04 | 復(fù)雜度分析（下）：淺析最好、最壞、平均、均攤時間復(fù)雜度
上一節(jié)，我們講了復(fù)雜度的大O表示法和幾個分析技巧，還舉了一些常見復(fù)雜度分析的例子，比如O(1)、O(logn)、O(n)、O(nlogn)復(fù)雜度分析。掌握了這些內(nèi)容，對于復(fù)雜度分析這個知識點，你已經(jīng)可以到及格線了。但是，我想你肯定不會滿足于此。
今天我會繼續(xù)給你講四個復(fù)雜度分析方面的知識點， 最好情況時間復(fù)雜度 （best case time complexity）、
最壞情況時間復(fù)雜度 （worst case time complexity）、 平均情況時間復(fù)雜度 （average case time
complexity）、 均攤時間復(fù)雜度 （amortized time
complexity）。如果這幾個概念你都能掌握，那對你來說，復(fù)雜度分析這部分內(nèi)容就沒什么大問題了。
最好、最壞情況時間復(fù)雜度
上一節(jié)我舉的分析復(fù)雜度的例子都很簡單，今天我們來看一個稍微復(fù)雜的。你可以用我上節(jié)教你的分析技巧，自己先試著分析一下這段代碼的時間復(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;
}
你應(yīng)該可以看出來，這段代碼要實現(xiàn)的功能是，在一個無序的數(shù)組（array）中，查找變量x出現(xiàn)的位置。如果沒有找到，就返回-1。按照上節(jié)課講的分析方法，這段代碼的復(fù)雜度是O(n)，其中，n代表數(shù)組的長度。
我們在數(shù)組中查找一個數(shù)據(jù)，并不需要每次都把整個數(shù)組都遍歷一遍，因為有可能中途找到就可以提前結(jié)束循環(huán)了。但是，這段代碼寫得不夠高效。我們可以這樣優(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;
}
}
return pos;
}
這個時候，問題就來了。我們優(yōu)化完之后，這段代碼的時間復(fù)雜度還是O(n)嗎？很顯然，咱們上一節(jié)講的分析方法，解決不了這個問題。
因為，要查找的變量x可能出現(xiàn)在數(shù)組的任意位置。如果數(shù)組中第一個元素正好是要查找的變量x，那就不需要繼續(xù)遍歷剩下的n-1個數(shù)據(jù)了，那時間復(fù)雜度就是O(1)。但如果數(shù)組中不存在變量x，那我們就需要把整個數(shù)組都遍歷一遍，時間復(fù)雜度就成了O(n)。所以，不同的情況下，這段代碼的時間復(fù)雜度是不一樣的。
為了表示代碼在不同情況下的不同時間復(fù)雜度，我們需要引入三個概念：最好情況時間復(fù)雜度、最壞情況時間復(fù)雜度和平均情況時間復(fù)雜度。
顧名思義， 最好情況時間復(fù)雜度就是，在最理想的情況下，執(zhí)行這段代碼的時間復(fù)雜度
。就像我們剛剛講到的，在最理想的情況下，要查找的變量x正好是數(shù)組的第一個元素，這個時候?qū)?yīng)的時間復(fù)雜度就是最好情況時間復(fù)雜度。
同理， 最壞情況時間復(fù)雜度就是，在最糟糕的情況下，執(zhí)行這段代碼的時間復(fù)雜度
。就像剛舉的那個例子，如果數(shù)組中沒有要查找的變量x，我們需要把整個數(shù)組都遍歷一遍才行，所以這種最糟糕情況下對應(yīng)的時間復(fù)雜度就是最壞情況時間復(fù)雜度。
平均情況時間復(fù)雜度
我們都知道，最好情況時間復(fù)雜度和最壞情況時間復(fù)雜度對應(yīng)的都是極端情況下的代碼復(fù)雜度，發(fā)生的概率其實并不大。為了更好地表示平均情況下的復(fù)雜度，我們需要引入另一個概念：平均情況時間復(fù)雜度，后面我簡稱為平均時間復(fù)雜度。
平均時間復(fù)雜度又該怎么分析呢？我還是借助剛才查找變量x的例子來給你解釋。
要查找的變量x在數(shù)組中的位置，有n+1種情況： 在數(shù)組的0～n-1位置中 和 不在數(shù)組中
。我們把每種情況下，查找需要遍歷的元素個數(shù)累加起來，然后再除以n+1，就可以得到需要遍歷的元素個數(shù)的平均值，即：
我們知道，時間復(fù)雜度的大O標(biāo)記法中，可以省略掉系數(shù)、低階、常量，所以，咱們把剛剛這個公式簡化之后，得到的平均時間復(fù)雜度就是O(n)。
這個結(jié)論雖然是正確的，但是計算過程稍微有點兒問題。究竟是什么問題呢？我們剛講的這n+1種情況，出現(xiàn)的概率并不是一樣的。我?guī)憔唧w分析一下。（這里要稍微用到一點兒概率論的知識，不過非常簡單，你不用擔(dān)心。）
我們知道，要查找的變量x，要么在數(shù)組里，要么就不在數(shù)組里。這兩種情況對應(yīng)的概率統(tǒng)計起來很麻煩，為了方便你理解，我們假設(shè)在數(shù)組中與不在數(shù)組中的概率都為1/2。另外，要查找的數(shù)據(jù)出現(xiàn)在0～n-1這n個位置的概率也是一樣的，為1/n。所以，根據(jù)概率乘法法則，要查找的數(shù)據(jù)出現(xiàn)在0～n-1中任意位置的概率就是1/(2n)。
因此，前面的推導(dǎo)過程中存在的最大問題就是，沒有將各種情況發(fā)生的概率考慮進去。如果我們把每種情況發(fā)生的概率也考慮進去，那平均時間復(fù)雜度的計算過程就變成了這樣：
這個值就是概率論中的 加權(quán)平均值 ，也叫作 期望值 ，所以平均時間復(fù)雜度的全稱應(yīng)該叫 加權(quán)平均時間復(fù)雜度 或者
期望時間復(fù)雜度 。
引入概率之后，前面那段代碼的加權(quán)平均值為(3n+1)/4。用大O表示法來表示，去掉系數(shù)和常量，這段代碼的加權(quán)平均時間復(fù)雜度仍然是O(n)。
你可能會說，平均時間復(fù)雜度分析好復(fù)雜啊，還要涉及概率論的知識。實際上，在大多數(shù)情況下，我們并不需要區(qū)分最好、最壞、平均情況時間復(fù)雜度三種情況。像我們上一節(jié)課舉的那些例子那樣，很多時候，我們使用一個復(fù)雜度就可以滿足需求了。只有同一塊代碼在不同的情況下，時間復(fù)雜度有量級的差距，我們才會使用這三種復(fù)雜度表示法來區(qū)分。
均攤時間復(fù)雜度
到此為止，你應(yīng)該已經(jīng)掌握了算法復(fù)雜度分析的大部分內(nèi)容了。下面我要給你講一個更加高級的概念，均攤時間復(fù)雜度，以及它對應(yīng)的分析方法，攤還分析（或者叫平攤分析）。
均攤時間復(fù)雜度，聽起來跟平均時間復(fù)雜度有點兒像。對于初學(xué)者來說，這兩個概念確實非常容易弄混。我前面說了，大部分情況下，我們并不需要區(qū)分最好、最壞、平均三種復(fù)雜度。平均復(fù)雜度只在某些特殊情況下才會用到，而均攤時間復(fù)雜度應(yīng)用的場景比它更加特殊、更加有限。
老規(guī)矩，我還是借助一個具體的例子來幫助你理解。（當(dāng)然，這個例子只是我為了方便講解想出來的，實際上沒人會這么寫。）
// array表示一個長度為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;
}
我先來解釋一下這段代碼。這段代碼實現(xiàn)了一個往數(shù)組中插入數(shù)據(jù)的功能。當(dāng)數(shù)組滿了之后，也就是代碼中的count ==
array.length時，我們用for循環(huán)遍歷數(shù)組求和，并清空數(shù)組，將求和之后的sum值放到數(shù)組的第一個位置，然后再將新的數(shù)據(jù)插入。但如果數(shù)組一開始就有空閑空間，則直接將數(shù)據(jù)插入數(shù)組。
那這段代碼的時間復(fù)雜度是多少呢？你可以先用我們剛講到的三種時間復(fù)雜度的分析方法來分析一下。
最理想的情況下，數(shù)組中有空閑空間，我們只需要將數(shù)據(jù)插入到數(shù)組下標(biāo)為count的位置就可以了，所以最好情況時間復(fù)雜度為O(1)。最壞的情況下，數(shù)組中沒有空閑空間了，我們需要先做一次數(shù)組的遍歷求和，然后再將數(shù)據(jù)插入，所以最壞情況時間復(fù)雜度為O(n)。
那平均時間復(fù)雜度是多少呢？答案是O(1)。我們還是可以通過前面講的概率論的方法來分析。
假設(shè)數(shù)組的長度是n，根據(jù)數(shù)據(jù)插入的位置的不同，我們可以分為n種情況，每種情況的時間復(fù)雜度是O(1)。除此之外，還有一種“額外”的情況，就是在數(shù)組沒有空閑空間時插入一個數(shù)據(jù)，這個時候的時間復(fù)雜度是O(n)。而且，這n+1種情況發(fā)生的概率一樣，都是1/(n+1)。所以，根據(jù)加權(quán)平均的計算方法，我們求得的平均時間復(fù)雜度就是：
至此為止，前面的最好、最壞、平均時間復(fù)雜度的計算，理解起來應(yīng)該都沒有問題。但是這個例子里的平均復(fù)雜度分析其實并不需要這么復(fù)雜，不需要引入概率論的知識。這是為什么呢？我們先來對比一下這個insert()的例子和前面那個find()的例子，你就會發(fā)現(xiàn)這兩者有很大差別。
首先，find()函數(shù)在極端情況下，復(fù)雜度才為O(1)。但insert()在大部分情況下，時間復(fù)雜度都為O(1)。只有個別情況下，復(fù)雜度才比較高，為O(n)。這是insert()
第一個 區(qū)別于find()的地方。
我們再來看 第二個
不同的地方。對于insert()函數(shù)來說，O(1)時間復(fù)雜度的插入和O(n)時間復(fù)雜度的插入，出現(xiàn)的頻率是非常有規(guī)律的，而且有一定的前后時序關(guān)系，一般都是一個O(n)插入之后，緊跟著n-1個O(1)的插入操作，循環(huán)往復(fù)。
所以，針對這樣一種特殊場景的復(fù)雜度分析，我們并不需要像之前講平均復(fù)雜度分析方法那樣，找出所有的輸入情況及相應(yīng)的發(fā)生概率，然后再計算加權(quán)平均值。
針對這種特殊的場景，我們引入了一種更加簡單的分析方法： 攤還分析法 ，通過攤還分析得到的時間復(fù)雜度我們起了一個名字，叫 均攤時間復(fù)雜度 。
那究竟如何使用攤還分析法來分析算法的均攤時間復(fù)雜度呢？
我們還是繼續(xù)看在數(shù)組中插入數(shù)據(jù)的這個例子。每一次O(n)的插入操作，都會跟著n-1次O(1)的插入操作，所以把耗時多的那次操作均攤到接下來的n-1次耗時少的操作上，均攤下來，這一組連續(xù)的操作的均攤時間復(fù)雜度就是O(1)。這就是均攤分析的大致思路。你都理解了嗎？
均攤時間復(fù)雜度和攤還分析應(yīng)用場景比較特殊，所以我們并不會經(jīng)常用到。為了方便你理解、記憶，我這里簡單總結(jié)一下它們的應(yīng)用場景。如果你遇到了，知道是怎么回事兒就行了。
對一個數(shù)據(jù)結(jié)構(gòu)進行一組連續(xù)操作中，大部分情況下時間復(fù)雜度都很低，只有個別情況下時間復(fù)雜度比較高，而且這些操作之間存在前后連貫的時序關(guān)系，這個時候，我們就可以將這一組操作放在一塊兒分析，看是否能將較高時間復(fù)雜度那次操作的耗時，平攤到其他那些時間復(fù)雜度比較低的操作上。而且，在能夠應(yīng)用均攤時間復(fù)雜度分析的場合，一般均攤時間復(fù)雜度就等于最好情況時間復(fù)雜度。
盡管很多數(shù)據(jù)結(jié)構(gòu)和算法書籍都花了很大力氣來區(qū)分平均時間復(fù)雜度和均攤時間復(fù)雜度，但其實我個人認(rèn)為， 均攤時間復(fù)雜度就是一種特殊的平均時間復(fù)雜度
，我們沒必要花太多精力去區(qū)分它們。你最應(yīng)該掌握的是它的分析方法，攤還分析。至于分析出來的結(jié)果是叫平均還是叫均攤，這只是個說法，并不重要。
內(nèi)容小結(jié)
今天我們學(xué)習(xí)了幾個復(fù)雜度分析相關(guān)的概念，分別有：最好情況時間復(fù)雜度、最壞情況時間復(fù)雜度、平均情況時間復(fù)雜度、均攤時間復(fù)雜度。之所以引入這幾個復(fù)雜度概念，是因為，同一段代碼，在不同輸入的情況下，復(fù)雜度量級有可能是不一樣的。
在引入這幾個概念之后，我們可以更加全面地表示一段代碼的執(zhí)行效率。而且，這幾個概念理解起來都不難。最好、最壞情況下的時間復(fù)雜度分析起來比較簡單，但平均、均攤兩個復(fù)雜度分析相對比較復(fù)雜。如果你覺得理解得還不是很深入，不用擔(dān)心，在后續(xù)具體的數(shù)據(jù)結(jié)構(gòu)和算法學(xué)習(xí)中，我們可以繼續(xù)慢慢實踐！
分析一下下面這個add()函數(shù)的時間復(fù)雜度。
// 全局變量，大小為10的數(shù)組array，長度len，下標(biāo)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復(fù)制給array，array現(xiàn)在大小就是2倍len了
array = new_array;
len = 2 * len;
}
// 將element放到下標(biāo)為i的位置，下標(biāo)i加一
array[i] = element;
++i;
}
歡迎留言和我分享，我會第一時間給你反饋。
