04 | 復(fù)雜度分析（下）：淺析最好蕉陋、最壞浓冒、平均彪笼、均攤時(shí)間復(fù)雜度
- 最好情況時(shí)間復(fù)雜度（best case time complexity）
- 最壞情況時(shí)間復(fù)雜度（worst case time complexity）
- 平均情況時(shí)間復(fù)雜度（average case time complexity）
- 均攤時(shí)間復(fù)雜度（amortized time complexity）
最好、最壞情況時(shí)間復(fù)雜度
// n 表示數(shù)組 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;
}
return pos;
}
以上代碼篮撑，是在一個(gè)無序數(shù)組 array 中屁使，查找變量 x 出現(xiàn)的位置在岂，找不到則返回 -1。
在數(shù)組中查找一個(gè)數(shù)據(jù)蛮寂，并不需要每次都把整個(gè)數(shù)組遍歷一遍蔽午，因此這段代碼可優(yōu)化為：
// n 表示數(shù)組 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; // 找到即可提前結(jié)束循環(huán)
}
}
return pos;
}
現(xiàn)在這段代碼的時(shí)間復(fù)雜度還是 O(n) 么？
- 當(dāng)數(shù)組中第一個(gè)元素剛好是要查找的變量 x 共郭，那此時(shí)的時(shí)間復(fù)雜度就是
O(1) - 當(dāng)數(shù)組中不存在變量 x 祠丝，那么整個(gè)數(shù)組都需要遍歷一遍疾呻，時(shí)間復(fù)雜度是
O(n)
為了表示代碼在不同情況下的不同時(shí)間復(fù)雜度，引入三個(gè)概念：最好情況時(shí)間復(fù)雜度写半、最壞情況時(shí)間復(fù)雜度岸蜗、平均情況時(shí)間復(fù)雜度
平均情況時(shí)間復(fù)雜度
從上面的例子看，想要查找變量 x 在數(shù)組中的位置叠蝇，有 n + 1 種情況：在數(shù)組的 0 ～ n - 1 位置 和 不在數(shù)組中璃岳。每種情況下，查找所需遍歷元素的個(gè)數(shù)累加 1 + 2 + 3 + ... + (n - 2) + (n - 1) + n + n 悔捶，除以 n + 1铃慷，就能得到需要遍歷元素個(gè)數(shù)的平均值，即 n(n+3)/2(n+1)蜕该，時(shí)間復(fù)雜度的大O表示法中犁柜，忽略系數(shù)、低階堂淡、常量馋缅，所以這個(gè)公式簡化后得到的平均情況時(shí)間復(fù)雜度為O(n)
但是，上述計(jì)算過程沒有將概率考慮進(jìn)去绢淀。??????考慮概率怎么計(jì)算呢......
設(shè)變量 x 在數(shù)組中的概率是 p 萤悴，則不在數(shù)組中的概率為 1-p，那么皆的，在數(shù)組中各個(gè)位置的概率應(yīng)均為 p/n
那么覆履，平均時(shí)間復(fù)雜度的計(jì)算過程應(yīng)該是這樣的：
1 * p/n + 2 * p/n + ... + (n-1) * p/n + n * p/n + n * (1-p)
經(jīng)計(jì)算，可簡化為：n(2-p)/2 + p/2费薄，這就是概率論中的加權(quán)平均值硝全，也叫作期望值，所以平均時(shí)間復(fù)雜度的全稱應(yīng)該是加權(quán)平均時(shí)間復(fù)雜度或者期望時(shí)間復(fù)雜度楞抡。
??注意：這里和王爭老師講的不一樣啦柳沙，王爭老師的計(jì)算結(jié)果是
(3n+1)/4，他的計(jì)算過程可理解為：為了計(jì)算方便拌倍，假設(shè)p=1/2，將其代入我的公式也可得出相同結(jié)果噪径。??
引入概率之后柱恤，用大O表示法表示，去掉公式n(2-p)/2 + p/2中的系數(shù) (2-p)/2 和常量 p/2 找爱，上例的加權(quán)平均時(shí)間復(fù)雜度仍然是 O(n)梗顺。
均攤時(shí)間復(fù)雜度
// array 表示一個(gè)長度為 n 的數(shù)組
// 代碼中的 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];
}
array[0] = sum;
count = 1;
}
array[count] = val;
++count;
}
這段代碼實(shí)現(xiàn)了往數(shù)組中插入數(shù)據(jù)的功能。如果數(shù)組滿了车摄，即 count == array.length 時(shí)寺谤，遍歷數(shù)組求各項(xiàng)和仑鸥，將 sum 放到數(shù)組第一個(gè)位置，然后將新的數(shù)據(jù)插入变屁。如果數(shù)組有空閑空間眼俊，則直接將數(shù)據(jù)插入數(shù)組。
- 最好情況時(shí)間復(fù)雜度：數(shù)組中有空閑空間粟关，只需將數(shù)據(jù)插入到數(shù)組下標(biāo)為 count 的位置疮胖，此時(shí)時(shí)間復(fù)雜度
O(1) - 最壞情況時(shí)間復(fù)雜度：數(shù)組中沒有空閑空間，需要遍歷數(shù)組求各項(xiàng)和闷板，再將數(shù)據(jù)插入澎灸，此時(shí)時(shí)間復(fù)雜度為
O(n) - 平均情況時(shí)間復(fù)雜度：數(shù)組長度是 n ，根據(jù)數(shù)據(jù)插入位置的不同遮晚，有n 種可能性性昭，這些情況的時(shí)間復(fù)雜度均為
O(1)；還有一種數(shù)組沒有空閑空間的情況县遣，這種情況的時(shí)間復(fù)雜度是O(n)糜颠。這 n+1 種情況發(fā)生的概率均為1/(n+1)。所以艺玲，根據(jù)加權(quán)平均的計(jì)算方法括蝠，求得平均時(shí)間復(fù)雜度是：
1 * 1/(n+1) + 1 * 1/(n+1) + ... + 1 * 1/(n+1) + n * 1/(n+1)，即O(1)
對比以上 find() 和 insert() 兩個(gè)函數(shù)：
-
find()函數(shù)最好情況下時(shí)間復(fù)雜度才為O(1)饭聚，其平均情況時(shí)間復(fù)雜度為O(n)忌警；而insert()函數(shù)的平均情況時(shí)間復(fù)雜度就是O(1)，只有個(gè)別情況下復(fù)雜度較高秒梳，為O(n)法绵。 - 對于
insert()來說，O(1)時(shí)間復(fù)雜度的插入和O(n)時(shí)間復(fù)雜度的插入酪碘，出現(xiàn)的頻率是有規(guī)律可循的朋譬，并且有一定的先后時(shí)序關(guān)系。一般是O(n)插入之后兴垦，緊跟著n - 1個(gè)O(1)的插入操作徙赢，循環(huán)往復(fù)。
所以探越，針對 insert() 函數(shù)這種特殊場景的復(fù)雜度分析狡赐，引入了更加簡單的分析方法：攤還分析法，通過攤還分析得到的時(shí)間復(fù)雜度叫作均攤時(shí)間復(fù)雜度钦幔。
均攤時(shí)間復(fù)雜度就是一種特殊的平均時(shí)間復(fù)雜度枕屉。
還看 insert() 函數(shù)這個(gè)例子，每一次 O(n) 插入之后鲤氢，都會跟著 n - 1 個(gè) O(1) 的插入操作搀擂，所以把耗時(shí)多的那次操作均攤到接下來的 n - 1 次耗時(shí)少的操作上西潘，均攤下來，這一組連續(xù)操作的均攤時(shí)間復(fù)雜度就是 O(1) 哨颂。這就是均攤分析的大致思路喷市。
均攤時(shí)間復(fù)雜度和攤還分析應(yīng)用場景比較特殊：
- 對一個(gè)數(shù)據(jù)結(jié)構(gòu)進(jìn)行一組連續(xù)操作中，大部分情況下時(shí)間復(fù)雜度都很低咆蒿，只有個(gè)別情況下時(shí)間復(fù)雜度比較高
- 這些操作之間存在前后連貫的時(shí)序關(guān)系
符合上面兩條的場景下东抹，可以將這一組操作一塊兒分析，看是否能將時(shí)間復(fù)雜度較高的那次操作的耗時(shí)分?jǐn)偟狡渌麜r(shí)間復(fù)雜度較低的操作上沃测。
在能夠應(yīng)用均攤時(shí)間復(fù)雜度分析的場合缭黔，一般均攤時(shí)間復(fù)雜度就等于最好情況時(shí)間復(fù)雜度。
課后思考
用今天學(xué)到的來分析一下下面代碼中 add() 函數(shù)的時(shí)間復(fù)雜度
// 全局變量蒂破，大小為 10 的數(shù)組 array馏谨，長度 len，下標(biāo) i 附迷。
int array[] = new int[10];
int len = 10;
int i = 0;
// 往數(shù)組中添加一個(gè)元素
void add(int element) {
if (i >= len) { // 數(shù)組空間不夠了
// 重新申請一個(gè) 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 復(fù)制給 array 惧互， array 現(xiàn)在大小就是 2 倍 len 了
array = new_array;
len = 2 * len;
}
// 將 element 放到下標(biāo)為 i 的位置，下標(biāo) i 加一
array[i] = element;
++i;
}
思考思考吧～??
