學好資料結構和演算法 —— 複雜度分析
複雜度也稱為漸進複雜度 ，包括漸進時間複雜度和漸進空間複雜度 ，描述演算法隨資料規模變化而逐漸變化的趨勢 。 複雜度分析是評估演算法好壞的基礎理論方法，所以掌握好複雜度分析方法是很有必要的。
時間複雜度
首先，學習資料結構是為了解決“快”和“省”的問題，那麼如何去評估演算法的速度快和省空間呢？這就需要掌握時間和空間複雜度分析。同一段程式碼執行在不同環境、不同配置機器、處理不同量級資料…效率肯定不會相同。時間複雜度和空間複雜度是不執行程式碼，從理論上粗略估計演算法執行效率的方法。時間複雜度 一般用O來表示，如下例子：計算1,2,3…n的和。CPU執行每行程式碼時間很快，假設每行執行時間都一樣 為 unit_time，第2行為一個 unit_time，第3、4行都執行了n遍，那麼下面這段程式碼執行的耗時時間可以這麼計算：(1+2*n) * unit_time。
1public int sum(int n) {
2int sum = 0;
3for (int i = 1; i <= n; i++) {
4sum = sum + i;
5}
6return sum;
7}
類似的再看一個例子：
1public int sum(int n) {
2int sum = 0;
3int i = 1;
4int j;
5for (; i <= n; i++) {
6j = 1;
7for (; j <= n; j++) {
8sum = sum + i * j;
9}
10}
11return sum;
12}
第2、3、4行分別執行執行了一次，時間為3unit_time，第5、6兩行迴圈了n次為2n * unit_time，第7、8兩行執行了n*n次為(n²) * unit_time，所以總的執行時間為：(2n²+2n+3) * unit_time
可以看出來，所有程式碼執行時間T(n)與每行程式碼執行次數成正比。可以用如下公式來表示：
T(n) = O(f(n))
T(n)表示程式碼的執行時間；
n表示資料規模大小；
f(n)表示每行程式碼執行的次數和，是一個表示式；
O表示執行時間T(n)和f(n)表示式成正比
那麼上面兩個時間複雜度可以表示為：
T(n) = O (1+2*n) 和 T(n) = O(2n²+2n+3)
實際上O並不表示具體的執行時間，只是表示程式碼執行時間隨資料規模變化的趨勢，所以時間複雜度實際上是漸進時間複雜度的簡稱。當n很大時，係數對結果的影響很小可以忽略，上面兩個例子的時間複雜度可以粗略簡化為：
T(n) = O (n) 和 T(n) = O(n²)
因為時間複雜度是表示的一種趨勢，所以常常忽略常量、低階、係數，只需要最大階量級就可以了。
分析時間複雜度的幾個常見法則
1、只關注程式碼執行最多的一段程式碼
上面例子可以看出，複雜度忽略了低階、常量和係數，所以執行最多的那一段最能表達時間複雜度的趨勢。
2、加法法則：總複雜度等於各部分求和，然後取複雜度量級最高的
還是上面的例子，總的時間複雜度等於各部分程式碼時間複雜度的和，求和之後再用最能表達趨勢的項來表示整段程式碼的時間複雜度。
3、乘法法則：巢狀程式碼複雜度等於巢狀內外程式碼複雜度的乘積
上面第二段程式碼，j 迴圈段巢狀在 i 迴圈內部，所以 j 迴圈體內的時間複雜度等於單獨 i 的時間複雜度乘以單獨 j 的時間複雜度。
常見的時間複雜度表示
常見的複雜度有以下幾種
- 常量階：O(1)
- 對數階：O(logn)
- 線性階：O(n)
- 線性對數階：O(nlogn)
- 平方階：O(n²)、立方階O(n³)……
- 指數階：O(2ⁿ)
- 階乘階：O(n!)
可以這麼來理解：如果一段程式碼有1000或10000行甚至更多，行數是一個常量，不會隨著資料規模增大而變化，我們就認為時間複雜度為一個常量，用O(1)表示。
這幾種複雜度效率曲線比較
模擬一個數組動態擴容例子，如果陣列長度夠，直接往裡面插入一條資料；反之，將陣列擴充一倍，然後往裡面插入一條資料：
1int[] arr = new int[10];
2int len = arr.length;
3int i = 0;
4public void add(int item) {
5if (i >= len) {
6int[] new_arr = new int[len * 2];
7for (int i = 0; i < len; i++) {
8new_arr[i] = arr[i];
9}
10arr = new_arr;
11len = arr.length;
12}
13arr[i] = item;
14i++;
15}
最好時間複雜度（best case time complexity）
最好情況下某個演算法的時間複雜度。最好情況下，陣列空間足夠，只需要執行插入資料就可以了，此時時間複雜度是O(1)。
最壞時間複雜度(worst case time complexity)
最壞情況下某個演算法的時間複雜度。最壞情況下陣列滿了，需要先申請一個空間為原來兩倍的陣列，然後將資料拷貝進去，此時時間複雜度為O(n)。一般情況下我們說演算法複雜度就是指的最壞情況時間複雜度，因為演算法時間複雜度不會比最壞情況複雜度更差了。
平均時間複雜度(average case time complexity)
最好時間複雜度和最壞時間複雜度都是極端情況下的時間複雜度，發生的概率並不算很大。平均時間複雜度是描述各種情況下平均的時間複雜度。上面的動態擴容例子將1到n+1次為一組來分析，前面n次的時間複雜度都是1，第n+1次時間複雜度是n，將一個數插入數組裡的1 至 (n+1)個位置概率都為1/(n+1)，所以平均時間複雜度為：
O(n) = (1 + 1 + 1 + …+n)/(n+1) = O(1)
均攤時間複雜度(amortized time complexity)
對一個數據結構進行一組連續的操作中，大部分情況下時間複雜度都很低，只有個別情況下時間複雜度比較高，而且這些操作之間存在前後連續的關係。並且和這組資料型別的情況迴圈往復出現，這時候可以將這一組資料作為一個整體來分析，看看是否可以將最後一個耗時的操作複雜度均攤到其他的操作上，如果可以，那麼這種分析方法就是均攤時間複雜度分析法。上面的例子來講，第n+1次插入資料時候，陣列剛好發生擴容，時間複雜度為O(n)，前面n次剛好將陣列填滿，每次時間複雜度都為O(1)，此時可以將第n+1次均攤到前面的n次上去，所以總的均攤時間複雜度還是O(1)。
空間複雜度
類比時間複雜度， 如下程式碼所示，第2行申請了一個長度為n的資料，第三行申請一個變數i為常量可以忽略，所以空間複雜度為O(n)
1public void init(int n) {
2int[] arr = new int[n];
3int i = 0;
4for (; i < n; i++) {
5arr[i] = i + 1;
6}
7}
一般情況下，一個程式在機器上執行時，除了需要儲存程式本身的指令、常數、變數和輸入資料外，還需要儲存對資料操作的儲存單元，若輸入資料所佔空間只取決於問題本身，和演算法無關，這樣只需要分析該演算法在實現時所需的輔助單元即可。若演算法執行時所需的輔助空間相對於輸入資料量而言是個常數，則稱此演算法為原地工作，空間複雜度為O(1)。