04| 復(fù)雜度分析（下）：淺析最好述暂、最壞痹升、平均、均攤時(shí)間復(fù)雜度
上一節(jié)畦韭，我們講了復(fù)雜度的大 O 表示法和幾個(gè)分析技巧疼蛾，還舉了一些常見復(fù)雜度分析的例子，比如 O(1) 艺配、 O(logn) 察郁、 O(n) 、 O(nlogn) 復(fù)雜度分析转唉。掌握了這些內(nèi)容皮钠，
對(duì)于復(fù)雜度分析這個(gè)知識(shí)點(diǎn)，你已經(jīng)可以到及格線了赠法。但是鳞芙，我想你肯定不會(huì)滿足于此。
今天我會(huì)繼續(xù)給你講四個(gè)復(fù)雜度分析方面的知識(shí)點(diǎn)，最好情況時(shí)間復(fù)雜度（best case time complexity）原朝、最壞情況時(shí)間復(fù)雜度（worst case time complexity）驯嘱、平均
情況時(shí)間復(fù)雜度（average case time complexity）、均攤時(shí)間復(fù)雜度（amortized time complexity）喳坠。如果這幾個(gè)概念你都能掌握鞠评，那對(duì)你來說，復(fù)雜度分析這部分內(nèi)
容就沒什么大問題了壕鹉。
最好剃幌、最壞情況時(shí)間復(fù)雜度
上一節(jié)我舉的分析復(fù)雜度的例子都很簡(jiǎn)單，今天我們來看一個(gè)稍微復(fù)雜的晾浴。你可以用我上節(jié)教你的分析技巧负乡，自己先試著分析一下這段代碼的時(shí)間復(fù)雜度。
// n表示數(shù)組array的長(zhǎng)度
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)該可以看出來脊凰，這段代碼要實(shí)現(xiàn)的功能是抖棘，在一個(gè)無序的數(shù)組（ array ）中，查找變量 x 出現(xiàn)的位置狸涌。如果沒有找到切省，就返回 -1 。按照上節(jié)課講的分析方法帕胆，這
段代碼的復(fù)雜度是 O(n) 朝捆，其中， n 代表數(shù)組的長(zhǎng)度懒豹。
我們?cè)跀?shù)組中查找一個(gè)數(shù)據(jù)芙盘，并不需要每次都把整個(gè)數(shù)組都遍歷一遍，因?yàn)橛锌赡苤型菊业骄涂梢蕴崆敖Y(jié)束循環(huán)了脸秽。但是儒老，這段代碼寫得不夠高效。我們可以這
樣優(yōu)化一下這段查找代碼豹储。
// n表示數(shù)組array的長(zhǎng)度
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;
}
這個(gè)時(shí)候贷盲，問題就來了。我們優(yōu)化完之后剥扣，這段代碼的時(shí)間復(fù)雜度還是 O(n) 嗎巩剖？很顯然，咱們上一節(jié)講的分析方法钠怯，解決不了這個(gè)問題佳魔。
因?yàn)椋檎业淖兞?x 可能出現(xiàn)在數(shù)組的任意位置晦炊。如果數(shù)組中第一個(gè)元素正好是要查找的變量 x 鞠鲜，那就不需要繼續(xù)遍歷剩下的 n-1 個(gè)數(shù)據(jù)了宁脊，那時(shí)間復(fù)雜度就
是 O(1) 。但如果數(shù)組中不存在變量 x 贤姆，那我們就需要把整個(gè)數(shù)組都遍歷一遍榆苞，時(shí)間復(fù)雜度就成了 O(n) 。所以霞捡，不同的情況下坐漏，這段代碼的時(shí)間復(fù)雜度是不一樣的。
為了表示代碼在不同情況下的不同時(shí)間復(fù)雜度碧信，我們需要引入三個(gè)概念：最好情況時(shí)間復(fù)雜度赊琳、最壞情況時(shí)間復(fù)雜度和平均情況時(shí)間復(fù)雜度。
顧名思義砰碴，最好情況時(shí)間復(fù)雜度就是躏筏，在最理想的情況下，執(zhí)行這段代碼的時(shí)間復(fù)雜度呈枉。就像我們剛剛講到的趁尼，在最理想的情況下，要查找的變量x正好是數(shù)組的
04|復(fù)雜度分析（下）：淺析最好碴卧、最壞弱卡、平均乃正、均攤時(shí)間復(fù)雜度
file:///F/temp/geektime/數(shù)據(jù)結(jié)構(gòu)與算法之美/04復(fù)雜度分析（下）：淺析最好住册、最壞、平均瓮具、均攤時(shí)間復(fù)雜度.html[2019/1/15 15:35:12]
第一個(gè)元素荧飞，這個(gè)時(shí)候?qū)?yīng)的時(shí)間復(fù)雜度就是最好情況時(shí)間復(fù)雜度。
同理名党，最壞情況時(shí)間復(fù)雜度就是叹阔，在最糟糕的情況下，執(zhí)行這段代碼的時(shí)間復(fù)雜度传睹。就像剛舉的那個(gè)例子耳幢，如果數(shù)組中沒有要查找的變量x，我們需要把整個(gè)數(shù)組
都遍歷一遍才行欧啤，所以這種最糟糕情況下對(duì)應(yīng)的時(shí)間復(fù)雜度就是最壞情況時(shí)間復(fù)雜度睛藻。
平均情況時(shí)間復(fù)雜度
我們都知道，最好情況時(shí)間復(fù)雜度和最壞情況時(shí)間復(fù)雜度對(duì)應(yīng)的都是極端情況下的代碼復(fù)雜度邢隧，發(fā)生的概率其實(shí)并不大店印。為了更好地表示平均情況下的復(fù)雜度，
我們需要引入另一個(gè)概念：平均情況時(shí)間復(fù)雜度倒慧，后面我簡(jiǎn)稱為平均時(shí)間復(fù)雜度按摘。
平均時(shí)間復(fù)雜度又該怎么分析呢包券？我還是借助剛才查找變量 x 的例子來給你解釋。
要查找的變量x在數(shù)組中的位置炫贤，有n+1種情況：在數(shù)組的0～n-1位置中和不在數(shù)組中溅固。我們把每種情況下，查找需要遍歷的元素個(gè)數(shù)累加起來兰珍，然后再除以n+1发魄，
就可以得到需要遍歷的元素個(gè)數(shù)的平均值，即：
我們知道俩垃，時(shí)間復(fù)雜度的大 O 標(biāo)記法中励幼，可以省略掉系數(shù)、低階口柳、常量苹粟，所以，咱們把剛剛這個(gè)公式簡(jiǎn)化之后跃闹，得到的平均時(shí)間復(fù)雜度就是 O(n) 嵌削。
這個(gè)結(jié)論雖然是正確的，但是計(jì)算過程稍微有點(diǎn)兒?jiǎn)栴}望艺。究竟是什么問題呢苛秕？我們剛講的這 n+1 種情況，出現(xiàn)的概率并不是一樣的找默。我?guī)憔唧w分析一下艇劫。（這里
要稍微用到一點(diǎn)兒概率論的知識(shí)，不過非常簡(jiǎn)單惩激，你不用擔(dān)心店煞。）
我們知道，要查找的變量 x 风钻，要么在數(shù)組里顷蟀，要么就不在數(shù)組里。這兩種情況對(duì)應(yīng)的概率統(tǒng)計(jì)起來很麻煩骡技，為了方便你理解鸣个，我們假設(shè)在數(shù)組中與不在數(shù)組中的概
率都為 1/2 。另外布朦，要查找的數(shù)據(jù)出現(xiàn)在 0 ～ n-1 這 n 個(gè)位置的概率也是一樣的囤萤，為 1/n 。所以喝滞，根據(jù)概率乘法法則阁将，要查找的數(shù)據(jù)出現(xiàn)在 0 ～ n-1 中任意位置的概率就
是 1/(2n) 。
因此右遭，前面的推導(dǎo)過程中存在的最大問題就是做盅，沒有將各種情況發(fā)生的概率考慮進(jìn)去缤削。如果我們把每種情況發(fā)生的概率也考慮進(jìn)去，那平均時(shí)間復(fù)雜度的計(jì)算過
程就變成了這樣：
04|復(fù)雜度分析（下）：淺析最好吹榴、最壞亭敢、平均、均攤時(shí)間復(fù)雜度
file:///F/temp/geektime/數(shù)據(jù)結(jié)構(gòu)與算法之美/04復(fù)雜度分析（下）：淺析最好图筹、最壞帅刀、平均、均攤時(shí)間復(fù)雜度.html[2019/1/15 15:35:12]
這個(gè)值就是概率論中的加權(quán)平均值远剩，也叫作期望值扣溺，所以平均時(shí)間復(fù)雜度的全稱應(yīng)該叫加權(quán)平均時(shí)間復(fù)雜度或者期望時(shí)間復(fù)雜度。
引入概率之后瓜晤，前面那段代碼的加權(quán)平均值為 (3n+1)/4 锥余。用大 O 表示法來表示，去掉系數(shù)和常量痢掠，這段代碼的加權(quán)平均時(shí)間復(fù)雜度仍然是 O(n) 驱犹。
你可能會(huì)說，平均時(shí)間復(fù)雜度分析好復(fù)雜啊足画，還要涉及概率論的知識(shí)雄驹。實(shí)際上，在大多數(shù)情況下淹辞，我們并不需要區(qū)分最好医舆、最壞、平均情況時(shí)間復(fù)雜度三種情
況桑涎。像我們上一節(jié)課舉的那些例子那樣彬向，很多時(shí)候兼贡，我們使用一個(gè)復(fù)雜度就可以滿足需求了攻冷。只有同一塊代碼在不同的情況下，時(shí)間復(fù)雜度有量級(jí)的差距遍希，我們
才會(huì)使用這三種復(fù)雜度表示法來區(qū)分等曼。
均攤時(shí)間復(fù)雜度
到此為止，你應(yīng)該已經(jīng)掌握了算法復(fù)雜度分析的大部分內(nèi)容了凿蒜。下面我要給你講一個(gè)更加高級(jí)的概念禁谦，均攤時(shí)間復(fù)雜度，以及它對(duì)應(yīng)的分析方法废封，攤還分析（或
者叫平攤分析）州泊。
均攤時(shí)間復(fù)雜度，聽起來跟平均時(shí)間復(fù)雜度有點(diǎn)兒像漂洋。對(duì)于初學(xué)者來說遥皂，這兩個(gè)概念確實(shí)非常容易弄混力喷。我前面說了，大部分情況下演训，我們并不需要區(qū)分最好弟孟、
最壞、平均三種復(fù)雜度样悟。平均復(fù)雜度只在某些特殊情況下才會(huì)用到拂募，而均攤時(shí)間復(fù)雜度應(yīng)用的場(chǎng)景比它更加特殊、更加有限窟她。
老規(guī)矩陈症，我還是借助一個(gè)具體的例子來幫助你理解。（當(dāng)然震糖，這個(gè)例子只是我為了方便講解想出來的爬凑，實(shí)際上沒人會(huì)這么寫。）
// array表示一個(gè)長(zhǎng)度為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)了一個(gè)往數(shù)組中插入數(shù)據(jù)的功能嘁信。當(dāng)數(shù)組滿了之后，也就是代碼中的 count == array.length 時(shí)疏叨，我們用 for 循環(huán)遍歷數(shù)組求
04|復(fù)雜度分析（下）：淺析最好潘靖、最壞、平均蚤蔓、均攤時(shí)間復(fù)雜度
file:///F/temp/geektime/數(shù)據(jù)結(jié)構(gòu)與算法之美/04復(fù)雜度分析（下）：淺析最好卦溢、最壞、平均秀又、均攤時(shí)間復(fù)雜度.html[2019/1/15 15:35:12]
和单寂，并清空數(shù)組，將求和之后的 sum 值放到數(shù)組的第一個(gè)位置，然后再將新的數(shù)據(jù)插入好芭。但如果數(shù)組一開始就有空閑空間残揉，則直接將數(shù)據(jù)插入數(shù)組。
那這段代碼的時(shí)間復(fù)雜度是多少呢尊沸？你可以先用我們剛講到的三種時(shí)間復(fù)雜度的分析方法來分析一下。
最理想的情況下贤惯，數(shù)組中有空閑空間洼专，我們只需要將數(shù)據(jù)插入到數(shù)組下標(biāo)為 count 的位置就可以了，所以最好情況時(shí)間復(fù)雜度為 O(1) 孵构。最壞的情況下屁商，數(shù)組中沒有
空閑空間了，我們需要先做一次數(shù)組的遍歷求和颈墅，然后再將數(shù)據(jù)插入蜡镶，所以最壞情況時(shí)間復(fù)雜度為 O(n) 溯职。
那平均時(shí)間復(fù)雜度是多少呢？答案是 O(1) 帽哑。我們還是可以通過前面講的概率論的方法來分析谜酒。
假設(shè)數(shù)組的長(zhǎng)度是 n ，根據(jù)數(shù)據(jù)插入的位置的不同妻枕，我們可以分為 n 種情況僻族，每種情況的時(shí)間復(fù)雜度是 O(1) 。除此之外屡谐，還有一種 “ 額外 ” 的情況述么，就是在數(shù)組沒有空
閑空間時(shí)插入一個(gè)數(shù)據(jù)，這個(gè)時(shí)候的時(shí)間復(fù)雜度是 O(n) 愕掏。而且度秘，這 n+1 種情況發(fā)生的概率一樣，都是 1/(n+1) 饵撑。所以剑梳，根據(jù)加權(quán)平均的計(jì)算方法，我們求得的平均時(shí)
間復(fù)雜度就是：
至此為止滑潘，前面的最好垢乙、最壞、平均時(shí)間復(fù)雜度的計(jì)算语卤，理解起來應(yīng)該都沒有問題追逮。但是這個(gè)例子里的平均復(fù)雜度分析其實(shí)并不需要這么復(fù)雜，不需要引入概率
論的知識(shí)粹舵。這是為什么呢钮孵？我們先來對(duì)比一下這個(gè) insert() 的例子和前面那個(gè) find() 的例子，你就會(huì)發(fā)現(xiàn)這兩者有很大差別眼滤。
首先巴席，find()函數(shù)在極端情況下，復(fù)雜度才為O(1)柠偶。但insert()在大部分情況下情妖，時(shí)間復(fù)雜度都為O(1)。只有個(gè)別情況下诱担，復(fù)雜度才比較高，為O(n)电爹。這是insert()第一
個(gè)區(qū)別于find()的地方蔫仙。
我們?cè)賮砜吹诙€(gè)不同的地方。對(duì)于insert()函數(shù)來說丐箩，O(1)時(shí)間復(fù)雜度的插入和O(n)時(shí)間復(fù)雜度的插入摇邦，出現(xiàn)的頻率是非常有規(guī)律的恤煞，而且有一定的前后時(shí)序關(guān)
系，一般都是一個(gè) O(n) 插入之后施籍，緊跟著 n-1 個(gè) O(1) 的插入操作居扒，循環(huán)往復(fù)。
所以丑慎，針對(duì)這樣一種特殊場(chǎng)景的復(fù)雜度分析喜喂，我們并不需要像之前講平均復(fù)雜度分析方法那樣，找出所有的輸入情況及相應(yīng)的發(fā)生概率竿裂，然后再計(jì)算加權(quán)平均
值玉吁。
針對(duì)這種特殊的場(chǎng)景，我們引入了一種更加簡(jiǎn)單的分析方法：攤還分析法腻异，通過攤還分析得到的時(shí)間復(fù)雜度我們起了一個(gè)名字进副，叫均攤時(shí)間復(fù)雜度。
那究竟如何使用攤還分析法來分析算法的均攤時(shí)間復(fù)雜度呢悔常？
我們還是繼續(xù)看在數(shù)組中插入數(shù)據(jù)的這個(gè)例子影斑。每一次 O(n) 的插入操作，都會(huì)跟著 n-1 次 O(1) 的插入操作机打，所以把耗時(shí)多的那次操作均攤到接下來的 n-1 次耗時(shí)少的
操作上鸥昏，均攤下來，這一組連續(xù)的操作的均攤時(shí)間復(fù)雜度就是 O(1) 姐帚。這就是均攤分析的大致思路吏垮。你都理解了嗎？
均攤時(shí)間復(fù)雜度和攤還分析應(yīng)用場(chǎng)景比較特殊罐旗，所以我們并不會(huì)經(jīng)常用到膳汪。為了方便你理解、記憶九秀，我這里簡(jiǎn)單總結(jié)一下它們的應(yīng)用場(chǎng)景遗嗽。如果你遇到了，知道
是怎么回事兒就行了鼓蜒。
對(duì)一個(gè)數(shù)據(jù)結(jié)構(gòu)進(jìn)行一組連續(xù)操作中痹换，大部分情況下時(shí)間復(fù)雜度都很低，只有個(gè)別情況下時(shí)間復(fù)雜度比較高都弹，而且這些操作之間存在前后連貫的時(shí)序關(guān)系娇豫，這個(gè)
時(shí)候，我們就可以將這一組操作放在一塊兒分析畅厢，看是否能將較高時(shí)間復(fù)雜度那次操作的耗時(shí)冯痢，平攤到其他那些時(shí)間復(fù)雜度比較低的操作上。而且，在能夠應(yīng)用
04|復(fù)雜度分析（下）：淺析最好浦楣、最壞袖肥、平均、均攤時(shí)間復(fù)雜度
file:///F/temp/geektime/數(shù)據(jù)結(jié)構(gòu)與算法之美/04復(fù)雜度分析（下）：淺析最好振劳、最壞椎组、平均、均攤時(shí)間復(fù)雜度.html[2019/1/15 15:35:12]
均攤時(shí)間復(fù)雜度分析的場(chǎng)合历恐，一般均攤時(shí)間復(fù)雜度就等于最好情況時(shí)間復(fù)雜度寸癌。
盡管很多數(shù)據(jù)結(jié)構(gòu)和算法書籍都花了很大力氣來區(qū)分平均時(shí)間復(fù)雜度和均攤時(shí)間復(fù)雜度，但其實(shí)我個(gè)人認(rèn)為夹供，均攤時(shí)間復(fù)雜度就是一種特殊的平均時(shí)間復(fù)雜度灵份，
我們沒必要花太多精力去區(qū)分它們。你最應(yīng)該掌握的是它的分析方法哮洽，攤還分析填渠。至于分析出來的結(jié)果是叫平均還是叫均攤，這只是個(gè)說法鸟辅，并不重要氛什。
