前一篇文章算法復雜度分析（上）講述了復雜度的大 O 表示法和幾個分析原則，這篇文章我們來講講另外幾種復雜度，最好情況時間復雜度（best case time complexity）、最壞情況時間復雜度（worst case time complexity）、平均時間復雜度（average case time complexity）和均攤時間復雜度（amortized time complexity）。

最好、最壞情況時間復雜度

顧名思義，這兩種時間復雜度指的是特殊情況下的時間復雜度。我們看下面的例子：

// n 表示數組 array 的長度
int find(int[] array, int n, int x) {int i = 0;int pos = -1;for (; i < n; ++i) {if (array[i] == x) {pos = i;break;}}return pos;
}
復制代碼

這段代碼實現的功能是，在數組 array 中尋找變量 x 第一次出現的位置，若沒有找到，則返回 -1；否則返回位置下標。

用上一篇文章的方法顯然是無法分析這段代碼的復雜度的。因為，不同情況下的時間復雜度是不同的。當數組中第一個元素就是要找的 x 時，時間復雜度是 O(1)；而當最后一個元素才是 x 時，時間復雜度則是 O(n)。

為了表示代碼在不同情況下的時間復雜度，就需要引入三個概念：最好情況時間復雜度、最壞情況時間復雜度和平均情況時間復雜度。

其中，最好情況時間復雜度就是在最理想情況下執行代碼的時間復雜度，它的時間是最短的；最壞情況時間復雜度就是在最糟糕情況下執行代碼的時間復雜度，它的時間是最長的。

平均情況時間復雜度

最好、最壞時間復雜度反應的是極端條件下的復雜度，發生的概率不大，不能代表平均水平。那么為了更好的表示平均情況下的算法復雜度，就需要引入平均時間復雜度。

繼續用前面 find 函數為例，假設變量 x 在和不在數組 array 中的概率分別為 1 / 2；當存在于數組中時，在每個位置的概率均等，為 1 / n。那么，平均情況時間復雜度就可以用下面的方式計算：

((1 + 2 + ... + n) / n + n) / 2 = (3n + 1) / 4

這個值就是概率論中的加權平均值，也叫期望值。所以平均情況時間復雜度也叫加權平均時間復雜度或期望時間復雜度。可見，find 函數的平均時間復雜度為 O(n)。

大多數情況下，不需要區分最好、最壞、平均情況時間復雜度，只用一個復雜度就可以滿足需求了。只有當同一塊代碼在不同情況下，時間復雜度有數量級上的區別時，才需要考慮這三種復雜度。

均攤時間復雜度

由上面我們可以知道，平均時間復雜度只有在某些特殊的時候才會用到。均攤時間復雜度的應用場景比它更為特殊。均攤時間復雜度是指，當大部分情況下時間復雜度都很低，只有個別情況下時間復雜度比較高時，并且這些操作之間存在著前后連貫的時序關系，這時候，可以將較高時間復雜度的操作耗時均攤至時間復雜度較低的操作上。這種分析方法叫做攤還分析法，得到的復雜度叫做均攤時間復雜度。

而且，在能夠應用均攤時間復雜度分析的場合，一般均攤時間復雜度就等于最好情況時間復雜度。

例如：

int[] array = new int(n);
int count = 0;void addLast (int val) {if (count == array.length) {int[] newArray = new int(2 * n);for (int i = 0; i < 2 * n; i++) {newArray[i] = array[i];}newArray[count] = val;array = newArray;} else {array[count] = val}count++;
}
復制代碼

這段代碼實現的功能是往數組的末尾增加一個元素，如果數組沒有滿，直接往后面插入元素；如果數組滿了，即 count == array.length，則將數組擴容一倍，然后再插入元素。

例如，數組長度為 n，則前 n 次調用 addLast() 復雜度都為 O(1)；第 n + 1 次則需要先進行 n 次元素轉移操作，然后再進行 1 次插入操作，復雜度為 O(n)。而且很容易看出，O(1) 復雜度的操作和 O(n) 復雜度的操作出現頻率是有規律的，每 n 次 O(1) 操作后會跟隨一個 O(n) 操作。

那么，就可以將 O(n) 操作的復雜度均攤至每次 O(1) 操作中，均攤下來，這組操作的需要進行 (n + n * 1) / (n + 1) = 2n / (n + 1) 次操作，所以均攤復雜度為 O(1)。

---

本文首發自微信公眾號《代碼寫完了》