注：本文僅為筆記。

原文

極客時間 - 數據結構與算法之美 - 04 | 復雜度分析（下）：淺析最好、最壞、平均、均攤時間復雜度

最好、最壞時間復雜度

略，比較容易分析。

平均時間復雜度

需考慮概率來計算。

概率論中的加權平均值，也叫作期望值，所以平均時間復雜度的全稱應該叫加權平均時間復雜度或者期望時間復雜度。

均攤時間復雜度

均攤時間復雜度及對應的攤還分析法。

對一個數據結構進行一組連續操作中，大部分情況下時間復雜度都很低，只有個別情況下時間復雜度比較高，而且這些操作之間存在前后連貫的時序關系，這個時候，我們就可以將這一組操作放在一塊兒分析，看是否能將較高時間復雜度那次操作的耗時，平攤到其他那些時間復雜度比較低的操作上。而且，在能夠應用均攤時間復雜度分析的場合，一般均攤時間復雜度就等于最好情況時間復雜度。

// 全局變量，大小為 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_arrayfor (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;
}