淺析最好，最壞讯榕，平均骤素，均攤時間復雜度
今天我會繼續(xù)給你講四個復雜度分析方面的知識點，最好情況時間復雜度（best case time complexity）愚屁、最壞情況時間復雜度（worst case time complexity）济竹、平均情況時間復雜度（average case time complexity）、均攤時間復雜度（amortized time complexity）霎槐。如果這幾個概念你都能掌握送浊，那對你來說，復雜度分析這部分內(nèi)容就沒什么大問題了丘跌。
最好袭景、最壞情況時間復雜度
上一節(jié)我舉的分析復雜度的例子都很簡單，今天我們來看一個稍微復雜的闭树。你可以用我上節(jié)教你的分析技巧耸棒，自己先試著分析一下這段代碼的時間復雜度。
// 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;
}
你應該可以看出來报辱，這段代碼要實現(xiàn)的功能是与殃，在一個無序的數(shù)組（array）中，查找變量 x 出現(xiàn)的位置。如果沒有找到幅疼，就返回 -1米奸。按照上節(jié)課講的分析方法，這段代碼的復雜度是 O(n)衣屏，其中躏升，n 代表數(shù)組的長度。
我們在數(shù)組中查找一個數(shù)據(jù)狼忱，并不需要每次都把整個數(shù)組都遍歷一遍膨疏，因為有可能中途找到就可以提前結束循環(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)化完之后，這段代碼的時間復雜度還是 O(n) 嗎瘤泪？很顯然灶泵，咱們上一節(jié)講的分析方法，解決不了這個問題对途。
因為赦邻，要查找的變量 x 可能出現(xiàn)在數(shù)組的任意位置。如果數(shù)組中第一個元素正好是要查找的變量 x实檀，那就不需要繼續(xù)遍歷剩下的 n-1 個數(shù)據(jù)了惶洲，那時間復雜度就是 O(1)。但如果數(shù)組中不存在變量 x膳犹，那我們就需要把整個數(shù)組都遍歷一遍恬吕，時間復雜度就成了 O(n)。所以须床，不同的情況下铐料，這段代碼的時間復雜度是不一樣的。
為了表示代碼在不同情況下的不同時間復雜度豺旬，我們需要引入三個概念：最好情況時間復雜度钠惩、最壞情況時間復雜度和平均情況時間復雜度。
顧名思義哈垢，最好情況時間復雜度就是妻柒，在最理想的情況下，執(zhí)行這段代碼的時間復雜度耘分。就像我們剛剛講到的举塔，在最理想的情況下绑警，要查找的變量 x 正好是數(shù)組的第一個元素，這個時候對應的時間復雜度就是最好情況時間復雜度央渣。
同理计盒，最壞情況時間復雜度就是，在最糟糕的情況下芽丹，執(zhí)行這段代碼的時間復雜度北启。就像剛舉的那個例子，如果數(shù)組中沒有要查找的變量 x拔第，我們需要把整個數(shù)組都遍歷一遍才行咕村，所以這種最糟糕情況下對應的時間復雜度就是最壞情況時間復雜度。
平均情況時間復雜度
我們都知道蚊俺，最好情況時間復雜度和最壞情況時間復雜度對應的都是極端情況下的代碼復雜度懈涛，發(fā)生的概率其實并不大。為了更好地表示平均情況下的復雜度泳猬，我們需要引入另一個概念：平均情況時間復雜度批钠，后面我簡稱為平均時間復雜度。
平均時間復雜度又該怎么分析呢得封？我還是借助剛才查找變量 x 的例子來給你解釋埋心。
要查找的變量 x 在數(shù)組中的位置，有 n+1 種情況：在數(shù)組的 0～n-1 位置中和不在數(shù)組中忙上。我們把每種情況下拷呆，查找需要遍歷的元素個數(shù)累加起來，然后再除以 n+1晨横，就可以得到需要遍歷的元素個數(shù)的平均值洋腮，即：
我們知道箫柳，時間復雜度的大 O 標記法中手形，可以省略掉系數(shù)、低階悯恍、常量库糠，所以，咱們把剛剛這個公式簡化之后涮毫，得到的平均時間復雜度就是 O(n)瞬欧。
這個結論雖然是正確的，但是計算過程稍微有點兒問題罢防。究竟是什么問題呢艘虎？我們剛講的這 n+1 種情況，出現(xiàn)的概率并不是一樣的咒吐。我?guī)憔唧w分析一下野建。（這里要稍微用到一點兒概率論的知識属划，不過非常簡單，你不用擔心候生。）
我們知道同眯，要查找的變量 x，要么在數(shù)組里唯鸭，要么就不在數(shù)組里须蜗。這兩種情況對應的概率統(tǒng)計起來很麻煩，為了方便你理解目溉，我們假設在數(shù)組中與不在數(shù)組中的概率都為 1/2明肮。另外，要查找的數(shù)據(jù)出現(xiàn)在 0～n-1 這 n 個位置的概率也是一樣的缭付，為 1/n晤愧。所以，根據(jù)概率乘法法則蛉腌，要查找的數(shù)據(jù)出現(xiàn)在 0～n-1 中任意位置的概率就是 1/(2n)官份。
因此，前面的推導過程中存在的最大問題就是烙丛，沒有將各種情況發(fā)生的概率考慮進去舅巷。如果我們把每種情況發(fā)生的概率也考慮進去，那平均時間復雜度的計算過程就變成了這樣
這個值就是概率論中的加權平均值河咽，也叫作期望值钠右，所以平均時間復雜度的全稱應該叫加權平均時間復雜度或者期望時間復雜度。
引入概率之后忘蟹，前面那段代碼的加權平均值為 (3n+1)/4飒房。用大 O 表示法來表示，去掉系數(shù)和常量媚值，這段代碼的加權平均時間復雜度仍然是 O(n)狠毯。
你可能會說，平均時間復雜度分析好復雜啊褥芒，還要涉及概率論的知識嚼松。實際上，在大多數(shù)情況下锰扶，我們并不需要區(qū)分最好献酗、最壞、平均情況時間復雜度三種情況坷牛。像我們上一節(jié)課舉的那些例子那樣罕偎，很多時候，我們使用一個復雜度就可以滿足需求了京闰。只有同一塊代碼在不同的情況下颜及，時間復雜度有量級的差距痴怨，我們才會使用這三種復雜度表示法來區(qū)分。
均攤時間復雜度
到此為止器予，你應該已經(jīng)掌握了算法復雜度分析的大部分內(nèi)容了浪藻。下面我要給你講一個更加高級的概念，均攤時間復雜度乾翔，以及它對應的分析方法爱葵，攤還分析（或者叫平攤分析）。
均攤時間復雜度反浓，聽起來跟平均時間復雜度有點兒像萌丈。對于初學者來說，這兩個概念確實非常容易弄混雷则。我前面說了辆雾，大部分情況下，我們并不需要區(qū)分最好月劈、最壞度迂、平均三種復雜度。平均復雜度只在某些特殊情況下才會用到猜揪，而均攤時間復雜度應用的場景比它更加特殊惭墓、更加有限。
老規(guī)矩而姐，我還是借助一個具體的例子來幫助你理解腊凶。（當然，這個例子只是我為了方便講解想出來的拴念，實際上沒人會這么寫钧萍。）
// 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ù)的功能政鼠。當數(shù)組滿了之后风瘦，也就是代碼中的 count == array.length 時，我們用 for 循環(huán)遍歷數(shù)組求和缔俄，并清空數(shù)組弛秋，將求和之后的 sum 值放到數(shù)組的第一個位置器躏，然后再將新的數(shù)據(jù)插入俐载。但如果數(shù)組一開始就有空閑空間，則直接將數(shù)據(jù)插入數(shù)組登失。
那這段代碼的時間復雜度是多少呢遏佣？你可以先用我們剛講到的三種時間復雜度的分析方法來分析一下。
最理想的情況下揽浙，數(shù)組中有空閑空間状婶，我們只需要將數(shù)據(jù)插入到數(shù)組下標為 count 的位置就可以了意敛，所以最好情況時間復雜度為 O(1)。最壞的情況下膛虫，數(shù)組中沒有空閑空間了草姻，我們需要先做一次數(shù)組的遍歷求和，然后再將數(shù)據(jù)插入稍刀，所以最壞情況時間復雜度為 O(n)撩独。
那平均時間復雜度是多少呢？答案是 O(1)账月。我們還是可以通過前面講的概率論的方法來分析综膀。
假設數(shù)組的長度是 n，根據(jù)數(shù)據(jù)插入的位置的不同局齿，我們可以分為 n 種情況剧劝，每種情況的時間復雜度是 O(1)。除此之外抓歼，還有一種“額外”的情況讥此，就是在數(shù)組沒有空閑空間時插入一個數(shù)據(jù)，這個時候的時間復雜度是 O(n)谣妻。而且暂论，這 n+1 種情況發(fā)生的概率一樣，都是 1/(n+1)拌禾。所以取胎，根據(jù)加權平均的計算方法，我們求得的平均時間復雜度就是：
至此為止湃窍，前面的最好闻蛀、最壞、平均時間復雜度的計算您市，理解起來應該都沒有問題觉痛。但是這個例子里的平均復雜度分析其實并不需要這么復雜，不需要引入概率論的知識茵休。這是為什么呢薪棒？我們先來對比一下這個 insert() 的例子和前面那個 find() 的例子，你就會發(fā)現(xiàn)這兩者有很大差別榕莺。
首先俐芯，find() 函數(shù)在極端情況下，復雜度才為 O(1)钉鸯。但 insert() 在大部分情況下吧史，時間復雜度都為 O(1)。只有個別情況下唠雕，復雜度才比較高贸营，為 O(n)吨述。這是 insert()第一個區(qū)別于 find() 的地方。
我們再來看第二個不同的地方钞脂。對于 insert() 函數(shù)來說揣云，O(1) 時間復雜度的插入和 O(n) 時間復雜度的插入，出現(xiàn)的頻率是非常有規(guī)律的冰啃，而且有一定的前后時序關系灵再，一般都是一個 O(n) 插入之后，緊跟著 n-1 個 O(1) 的插入操作亿笤，循環(huán)往復翎迁。
所以，針對這樣一種特殊場景的復雜度分析净薛，我們并不需要像之前講平均復雜度分析方法那樣汪榔，找出所有的輸入情況及相應的發(fā)生概率，然后再計算加權平均值肃拜。
針對這種特殊的場景痴腌，我們引入了一種更加簡單的分析方法：攤還分析法，通過攤還分析得到的時間復雜度我們起了一個名字燃领，叫均攤時間復雜度.
那究竟如何使用攤還分析法來分析算法的均攤時間復雜度呢士聪？
我們還是繼續(xù)看在數(shù)組中插入數(shù)據(jù)的這個例子。每一次 O(n) 的插入操作猛蔽，都會跟著 n-1 次 O(1) 的插入操作剥悟，所以把耗時多的那次操作均攤到接下來的 n-1 次耗時少的操作上，均攤下來曼库，這一組連續(xù)的操作的均攤時間復雜度就是 O(1)区岗。這就是均攤分析的大致思路。你都理解了嗎毁枯？
均攤時間復雜度和攤還分析應用場景比較特殊慈缔，所以我們并不會經(jīng)常用到。為了方便你理解种玛、記憶藐鹤，我這里簡單總結一下它們的應用場景。如果你遇到了赂韵，知道是怎么回事兒就行了娱节。
對一個數(shù)據(jù)結構進行一組連續(xù)操作中，大部分情況下時間復雜度都很低右锨，只有個別情況下時間復雜度比較高括堤，而且這些操作之間存在前后連貫的時序關系，這個時候绍移，我們就可以將這一組操作放在一塊兒分析悄窃，看是否能將較高時間復雜度那次操作的耗時，平攤到其他那些時間復雜度比較低的操作上蹂窖。而且轧抗，在能夠應用均攤時間復雜度分析的場合，一般均攤時間復雜度就等于最好情況時間復雜度瞬测。
盡管很多數(shù)據(jù)結構和算法書籍都花了很大力氣來區(qū)分平均時間復雜度和均攤時間復雜度横媚，但其實我個人認為，均攤時間復雜度就是一種特殊的平均時間復雜度月趟，我們沒必要花太多精力去區(qū)分它們灯蝴。你最應該掌握的是它的分析方法，攤還分析孝宗。至于分析出來的結果是叫平均還是叫均攤穷躁，這只是個說法，并不重要因妇。
內(nèi)容小結
今天我們學習了幾個復雜度分析相關的概念问潭，分別有：最好情況時間復雜度、最壞情況時間復雜度婚被、平均情況時間復雜度狡忙、均攤時間復雜度。之所以引入這幾個復雜度概念址芯，是因為灾茁，同一段代碼，在不同輸入的情況下谷炸，復雜度量級有可能是不一樣的删顶。
在引入這幾個概念之后，我們可以更加全面地表示一段代碼的執(zhí)行效率淑廊。而且逗余，這幾個概念理解起來都不難。最好季惩、最壞情況下的時間復雜度分析起來比較簡單录粱，但平均、均攤兩個復雜度分析相對比較復雜画拾。如果你覺得理解得還不是很深入啥繁，不用擔心，在后續(xù)具體的數(shù)據(jù)結構和算法學習中青抛，我們可以繼續(xù)慢慢實踐旗闽！
課后思考
我們今天學的幾個復雜度分析方法，你都掌握了嗎？你可以用今天學習的知識适室，來分析一下下面這個 add() 函數(shù)的時間復雜度嫡意。
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;
}
