課程：《復雜度分析（下）：淺析最好、最壞、平均、均攤時間復雜度》 總結(jié)
有時候，代碼的時間復雜度在不同情況下會出現(xiàn)量級的差異。為了更全面、更準確的描述代碼的時間復雜度，需要引入下面的概念。
四個復雜度分析的概念
-
最好情況時間復雜度（best case time complexity）
代碼在最理想的情況下執(zhí)行的時間復雜度。 -
最壞情況時間復雜度（worst case time complexity）
代碼在最糟糕的情況下執(zhí)行的時間復雜度。 -
平均情況時間復雜度（average case time complexity）
代碼在所有情況下的復雜度的加權(quán)平均值，即加權(quán)平均時間復雜度 或 期望時間復雜度 -
均攤時間復雜度（amortized time complexity）
在一組連續(xù)的具有時序關(guān)系的操作中，如果將這一組操作看成是一個整體，那么就可以將其中較高復雜度代碼的執(zhí)行時間平攤到復雜度較低的代碼上面。然后再進行復雜度分析后得出的就是均攤時間復雜度，這種分析方法叫做攤還分析。一般在這種特殊的場合中，均攤時間復雜度就是最好情況時間復雜度。
下面以課后題作為案例分析：
// 全局變量，大小為10的數(shù)組array，長度len，下標i。
int array[] = new int[10];
int len = 10;
int i = 0;
// 往數(shù)組中添加一個元素
void add(int element) {
if (i >= len) { // 數(shù)組空間不夠了
// 重新申請一個2倍大小的數(shù)組空間
int new_array[] = new int[len*2];
// 把原來array數(shù)組中的數(shù)據(jù)依次copy到new_array
for (int j = 0; j < len; ++j) {
new_array[j] = array[j];
}
// new_array復制給array，array現(xiàn)在大小就是2倍len了
array = new_array;
len = 2 * len;
}
// 將element放到下標為i的位置，下標i加一
array[i] = element;
++i;
}
最好情況時間復雜度
最好情況就是當前數(shù)組中有空間存放添加的數(shù)據(jù)，即直接執(zhí)行添加數(shù)據(jù)操作，這樣代碼的執(zhí)行次數(shù)總和為常量級，所以最好時間復雜度為O(1)。最壞情況時間復雜度
最壞的情況是數(shù)組已滿，需要重新申請兩倍新數(shù)組空間和循環(huán)拷貝當前數(shù)組的元素到新數(shù)組中。假設當前數(shù)組的長度為n，根據(jù)大O復雜度分析方法可得代碼的時間復雜度為O(n)。-
平均情況時間復雜度
分析可知，添加的元素可能存放的位置有1、2、3、4...n-1這n種情況，以及數(shù)組滿了需要新申請空間的情況，即總共n+1種情況，前面不需要申請空間的n種情況的時間復雜度都為O(1)，需要申請空間的情況下的時間復雜度（即最壞時間復雜度）為O(n)，假設每種情況的概率都相同，即1/(n+1)，那么平均時間復雜度就為：
平均時間復雜度 均攤時間復雜度
分析代碼可知，每進行n次O(1)的操作后，會緊跟一次O(n)的操作，如果將這些操作看作一個整體，將這一次O(n)的操作花費的時間平均在n次O(1)的操作上，也就相當于代碼多進行了一次O(1)的操作，即O(1) + O(1) = O(2) = O(1)。下面是我從時間復雜度表示的意義出發(fā)，做的分析：
我們知道大O時間復雜度表示的是代碼執(zhí)行時間隨數(shù)據(jù)規(guī)模增長的變化趨勢。從這個角度出發(fā)，看這段代碼。當數(shù)組的規(guī)模很大時，有足夠的空間來存放添加的數(shù)據(jù)，那么代碼的執(zhí)行次數(shù)就會是常量級的。所以均攤時間復雜度為O(1)，平均時間復雜度也為O(1).
上一篇：《數(shù)據(jù)結(jié)構(gòu)和算法之美》學習筆記 Day 2
下一篇：《數(shù)據(jù)結(jié)構(gòu)和算法之美》學習筆記 Day 4
