淺析最好、最壞、平均、均攤時間複雜度
最好、最壞時間複雜度#
舉例一段程式碼：
// 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;
}
這段程式碼的時間複雜度是 $O (n)$ 嗎？恐怕不是了。
當在這種情況下，程式碼的時間複雜度是需要分情況討論的，那麼就會有以下幾種時間複雜度：
最好情況時間複雜度：在理想情況下，執行這段程式碼的時間複雜度。在這個例子中，如果我們非常幸運，在 array [0] 就找到了這個數，那麼整段程式碼到這裡就停止了。此時，這段程式碼的時間複雜度為 $O (1)$。
最壞情況時間複雜度：在最糟糕的情況下，執行這段程式碼的時間複雜度。在這個例子中，如果我們非常不幸，在 array [n-1] 找到了，或者根本就沒找到這個數，那麼整段程式碼需要完整的遍歷這個陣列。此時，這段程式碼的時間複雜度為 $O (n)$。
平均時間複雜度#
那麼，最好情況時間複雜度和最壞情況時間複雜度，可能都太極端了，其發生的概率可能並不大，是不能客觀表示這段程式碼的時間複雜度的。那為了更好地表示平均情況下的複雜度，我們需要引入平均時間複雜度的概念。
回到上面那個例子中，變數 x 在陣列中的位置，可能會有 n+1 種情況：在陣列的 [0]~[n-1] 位置上(n) 或者不在陣列中(1)。我們把每種情況下，找出這個數所需要遍歷的元素個數累加起來，除以這 n+1 種情況，就可以得到為了找出這個數，需要遍歷的元素個數的平均值，也就是：
那麼，根據時間複雜度的大 O 標記法，係數、常數、低階皆可忽略。所以簡化之後，得到的平均時間複雜度就是 $O (n)$.
3月18日，存疑，到底是怎麼簡化的？搞不懂搞不懂。難道是這種分數形式就看最高階是什麼即可嗎？
3月19日，答疑，怎麼簡化的？根據leetcode裡大佬的解釋，舉一反三，可得n(n+3) / 2(n+1)展開為(n^2+3n) / (2n+2)，由於常數可忽略，所以可簡化為(n^2+3n) / (2n) = (n+3) / 2，所以化解之後的平均時間複雜度就是O(n)！！！
那麼，對於這個結論，還有一些小問題。變數 x 在陣列中的位置的 n+1 種情況，其發生概率並不是一樣的。
那麼首先，變數 x 在不在陣列裡？為了簡化，我們假設在陣列中與不在陣列中的概率都為 $1 \over 2$。另外，在陣列中出現在 [0]～[n-1] 這 n 個位置的概率也是一樣的，為 $1 \over n$。所以，根據概率乘法法則，要找的數據出現在 [0]~[n-1] 中任意位置的概率就是 $1 \over 2n$
那麼，這次我們將各種情況發生的概率考慮進去之後，平均複雜度的計算過程就變成了這樣：
這個值就是概率論中的加權平均值，也叫做期望值，所以平均時間複雜度的全稱應該叫加權平均時間複雜度或者期望時間複雜度
最後，這段程式碼的加權平均時間複雜度仍然是 $O (n)$。
實際上，在大多數情況下，我們並不需要區分最好、最壞、平均情況時間複雜度三種情況。只有同一塊程式碼在不同情況下，時間複雜度有量級的差距，我們才會使用這三種複雜度表示法來區分。
均攤時間複雜度#
我們舉一個例子：
// array表示一個長度為n的陣列
// 程式碼中的array.length就等於n
int[] array = new int[n];
int count = 0;
void insert(int val) {
if (count == array.length) {
int sum = 0;
for (int i = 0; i < array.length; ++i) {
sum = sum + array[i];
}
count = 1;//清空陣列
array[0] = sum;
}
array[count] = val;
++count;
}
這段程式碼的程式邏輯是：首先，這個函數的基本功能是向一個整型陣列中插入值。當陣列滿了之後，也就是 count == array.length 時，我們用 for 循環遍歷陣列求和，並清空陣列，將求和之後的 sum 值放到陣列 [0] 位置，然後再將要插入的 val 插入到 [count] 位置下。而當陣列沒有滿的時候，也就是 count != array.length 時，直接將數據插入陣列。
注意：此時清空陣列的操作是置count為1。對於可反復讀寫的存儲空間，使用者認為它是空的它就是空的。如果你定義空是指全部重寫為0或者某個值，那也可以！使用者應只關心要存的新值。
那麼，運用之前的三種時間複雜度的分析方法。
-
在最理想的情況下，陣列中有空閒空間 (陣列沒有滿)，我們只需要將數據插入到陣列 [count] 的位置下即可。最好情況時間複雜度為 $O (1)$。
-
在最糟糕的情況下，陣列沒有空閒空間 (陣列滿了)，我們需要做一次遍歷陣列求和，然後再插入值。最壞情況時間複雜度為 $O (n)$。
-
其平均時間複雜度，我們可以通過概率論的方法分析。假設陣列的長度是 n，根據數據插入的位置的不同，我們可以分為 n 種情況，每種情況的時間複雜度是 $O (1)$。除此之外，還有一種 “額外” 的情況，就是在陣列沒有空閒空間時插入一個數據，這個時候的時間複雜度是 $O (n)$。而且，這 n+1 種情況發生的概率是相同，都是 $1 \over n+1$。所以，根據加權平均的計算方法，我們求得的平均時間複雜度就是：
3月18日，存疑。為什麼左邊是 2n / n+1 。。。但是也可以算作O(n)啊？真的搞不懂。。。
3月19日，答疑。最後去Leetcode上請教大佬，大佬的說法是：“2n/(n+1)，上下的數量級為n，可以看成2n/n = 2，時間複雜度是常量級，所以為O(1)。”，看完簡直醍醐灌頂，茅塞頓開！
那麼實際上，我們不需要那麼複雜地求這個例子的平均複度。我們可以通過對比 find () 和 insert () 這兩個例子來看一看。
首先，find () 函數在極端情況下，複雜度才為 $O (1)$。但 insert () 函數在大部分情況下，時間複雜度都為 $O (1)$，只有在個別情況下，複雜度才比較高，為 $O (n)$。這是 insert ()第一個區別於 find () 地方。
第二。對於 insert () 函數來說，O (1) 時間複雜度的插入和 O (n) 時間複雜度的插入，出現的頻率是有規律可循的，有一定的前後時序關係。一般都是在 n-1 個 O (1) 的插入操作之後 (陣列未滿時插入數據)，緊跟著一個 O (n)(陣列滿時遍歷求和，清空陣列)，循環往復。
所以，針對這樣一種特殊場景的複雜度分析，我們引入了一種更加簡單的分析方法：攤還分析法，通過攤還分析得到的時間複雜度叫均攤時間複雜度。
通過例子來說明的話。每一次 O (n) 的插入操作，都会跟着 n-1 次 O (1) 的插入操作，所以耗時多的那次操作均攤到接下來的 n-1 次耗時少的操作上，均攤下來，這一組連續的操作的均攤時間複雜度就是 O (1).
平均時間複雜度和均攤時間複雜度的應用場景#
對一個數據結構進行一組連續操作時，大部分情況下時間複雜度都很低，只有個別情況下時間複雜度比較高，而且這些操作之間存在前後連貫的時序關係，這個時候，我們就可以將這一組操作放在一起分析，看是否能將較高時間複雜度那次操作的耗時，平攤到其他那些時間複雜度比較低的操作上。而且，在能夠應用均攤時間複雜度分析的場合，一般均攤時間複雜度就等於最好情況時間複雜度。
均攤時間複雜度就是一種特殊的平均時間複雜度
內容小結#
幾個複雜度分析相關的概念，分別有：最好情況時間複雜度、最壞情況時間複雜度、平均時間複雜度、均攤時間複雜度。之所以引入這幾個複雜度概念，是因為，同一段程式碼，在不同輸入的情況下，複雜度量級有可能是不一樣的 。在引入這幾個概念之後，可以更加全面地表示一段程式碼的執行效率。
課後思考題目#
// 全局變數，大小為10的陣列array，長度len，下標i。
int array[] = new int[10];
int len = 10;
int i = 0;
// 往陣列中添加一個元素
void add(int element) {
if (i >= len) { // 陣列空間不夠了
// 重新申請一個2倍大小的陣列空間
int new_array[] = new int[len*2];
// 把原來array陣列中的數據依次copy到new_array
for (int j = 0; j < len; ++j) {
new_array[j] = array[j];
}
// new_array複製給array，array現在大小就是2倍len了
array = new_array;
len = 2 * len;
}
// 將element放到下標為i的位置，下標i加一
array[i] = element;
++i;
}
這段程式碼的邏輯是：往陣列中添加一個元素，當陣列未滿時，直接插入；當陣列滿時，申請一個 2 倍大小的陣列空間，並把原陣列中的數據遍歷傳遞給新陣列，最後新陣列複製給原陣列，替代它。
在這段程式碼中，最好時間複雜度：是當陣列未滿時，直接插入。為 O (1);
最壞時間複雜度：是當陣列滿時，需要遍歷傳遞陣列。為 O (n);
平均時間複雜度：根據插入位置的不同 ，會有 n 種情況。另外，陣列滿時也有一種情況，而每種情況的概率都為 $1 \over n+1$。最後複雜度為 O (1);
均攤時間複雜度：每 n 個 O (1) 操作後都會緊跟一個 O (n) 操作，有時序關係，且可均攤，所以均攤時間複雜度為 O (1)。