『 算法之美 』復(fù)雜度分析春塌，看這里！
一簇捍、如何分析只壳、統(tǒng)計算法的執(zhí)行效率和資源消耗？
我們都知道暑塑，數(shù)據(jù)結(jié)構(gòu)和算法本身解決的是“快”和“省”的問題吼句，即如何讓代碼運(yùn)行得更快，如何讓代碼更省存儲空間事格。所以惕艳，執(zhí)行效率是算法一個非常重要的考量指標(biāo)搞隐。那如何來衡量你編寫的算法代碼的執(zhí)行效率呢？這里就要用到我們今天要講的內(nèi)容：時間远搪、空間復(fù)雜度分析劣纲。
其實(shí)，只要講到數(shù)據(jù)結(jié)構(gòu)與算法谁鳍，就一定離不開時間味廊、空間復(fù)雜度分析。而且棠耕，我個人認(rèn)為余佛，復(fù)雜度分析是整個算法學(xué)習(xí)的精髓，只要掌握了它窍荧，數(shù)據(jù)結(jié)構(gòu)和算法的內(nèi)容基本上就掌握了一半辉巡。
復(fù)雜度分析實(shí)在太重要了，因此我準(zhǔn)備用兩節(jié)內(nèi)容來講蕊退。希望你學(xué)完這個內(nèi)容之后郊楣，無論在任何場景下，面對任何代碼的復(fù)雜度分析瓤荔，你都能做到“庖丁解啪辉椋”般游刃有余。
為什么需要復(fù)雜度分析输硝？
你可能會有些疑惑今瀑，我把代碼跑一遍，通過統(tǒng)計点把、監(jiān)控橘荠，就能得到算法執(zhí)行的時間和占用的內(nèi)存大小。為什么還要做時間郎逃、空間復(fù)雜度分析呢哥童？這種分析方法能比我實(shí)實(shí)在在跑一遍得到的數(shù)據(jù)更準(zhǔn)確嗎？
首先褒翰，我可以肯定地說贮懈，你這種評估算法執(zhí)行效率的方法是正確的。很多數(shù)據(jù)結(jié)構(gòu)和算法書籍還給這種方法起了一個名字优训，叫事后統(tǒng)計法朵你。但是，這種統(tǒng)計方法有非常大的局限性型宙。
1. 測試結(jié)果非常依賴測試環(huán)境
測試環(huán)境中硬件的不同會對測試結(jié)果有很大的影響撬呢。比如，我們拿同樣一段代碼妆兑，分別用 Intel Core i9 處理器和 Intel Core i3 處理器來運(yùn)行魂拦，不用說毛仪，i9 處理器要比 i3 處理器執(zhí)行的速度快很多。還有芯勘，比如原本在這臺機(jī)器上 a 代碼執(zhí)行的速度比 b 代碼要快箱靴，等我們換到另一臺機(jī)器上時，可能會有截然相反的結(jié)果荷愕。
2. 測試結(jié)果受數(shù)據(jù)規(guī)模的影響很大
后面我們會講排序算法衡怀，我們先拿它舉個例子。對同一個排序算法安疗，待排序數(shù)據(jù)的有序度不一樣抛杨，排序的執(zhí)行時間就會有很大的差別。極端情況下荐类，如果數(shù)據(jù)已經(jīng)是有序的怖现，那排序算法不需要做任何操作，執(zhí)行時間就會非常短玉罐。除此之外屈嗤，如果測試數(shù)據(jù)規(guī)模太小，測試結(jié)果可能無法真實(shí)地反應(yīng)算法的性能吊输。比如饶号，對于小規(guī)模的數(shù)據(jù)排序，插入排序可能反倒會比快速排序要快季蚂！
所以茫船，我們需要一個不用具體的測試數(shù)據(jù)來測試，就可以粗略地估計算法的執(zhí)行效率的方法癣蟋。這就是我們今天要講的時間透硝、空間復(fù)雜度分析方法狰闪。
大 O 復(fù)雜度表示法
算法的執(zhí)行效率疯搅，粗略地講，就是算法代碼執(zhí)行的時間埋泵。但是幔欧，如何在不運(yùn)行代碼的情況下，用“肉眼”得到一段代碼的執(zhí)行時間呢丽声？
這里有段非常簡單的代碼礁蔗，求 1,2,3…n 的累加和。現(xiàn)在雁社，我就帶你一塊來估算一下這段代碼的執(zhí)行時間浴井。
1 int cal(int n) {
2 int sum = 0;
3 int i = 1;
4 for (; i <= n; ++i) {
5 sum = sum + i;
6 }
7 return sum;
8 }
從 CPU 的角度來看，這段代碼的每一行都執(zhí)行著類似的操作：讀數(shù)據(jù)-運(yùn)算-寫數(shù)據(jù)霉撵。盡管每行代碼對應(yīng)的 CPU 執(zhí)行的個數(shù)磺浙、執(zhí)行的時間都不一樣洪囤，但是，我們這里只是粗略估計撕氧，所以可以假設(shè)每行代碼執(zhí)行的時間都一樣瘤缩，為 unit_time。在這個假設(shè)的基礎(chǔ)之上伦泥，這段代碼的總執(zhí)行時間是多少呢剥啤？
第 2、3 行代碼分別需要 1 個 unit_time 的執(zhí)行時間不脯，第 4府怯、5 行都運(yùn)行了 n 遍，所以需要 2nunit_time 的執(zhí)行時間防楷，所以這段代碼總的執(zhí)行時間就是 (2n+2)unit_time富腊。可以看出來域帐，所有代碼的執(zhí)行時間 T(n) 與每行代碼的執(zhí)行次數(shù)成正比赘被。
按照這個分析思路，我們再來看這段代碼肖揣。
1 int cal(int n) {
2 int sum = 0;
3 int i = 1;
4 int j = 1;
5 for (; i <= n; ++i) {
6 j = 1;
7 for (; j <= n; ++j) {
8 sum = sum + i * j;
9 }
10 }
11 }
我們依舊假設(shè)每個語句的執(zhí)行時間是 unit_time民假。那這段代碼的總執(zhí)行時間 T(n) 是多少呢？
第 2龙优、3羊异、4 行代碼，每行都需要 1 個 unit_time 的執(zhí)行時間彤断，第 5野舶、6 行代碼循環(huán)執(zhí)行了 n 遍，需要 2n * unit_time 的執(zhí)行時間宰衙，第 7平道、8 行代碼循環(huán)執(zhí)行了 n2遍，所以需要 2n2 * unit_time 的執(zhí)行時間供炼。所以一屋，整段代碼總的執(zhí)行時間 T(n) = (2n2+2n+3)*unit_time。
盡管我們不知道 unit_time 的具體值袋哼，但是通過這兩段代碼執(zhí)行時間的推導(dǎo)過程冀墨，我們可以得到一個非常重要的規(guī)律，那就是涛贯，所有代碼的執(zhí)行時間 T(n) 與每行代碼的執(zhí)行次數(shù) n 成正比诽嘉。
我們可以把這個規(guī)律總結(jié)成一個公式。注意，大 O 就要登場了虫腋！
我來具體解釋一下這個公式身冬。其中，T(n) 我們已經(jīng)講過了岔乔，它表示代碼執(zhí)行的時間酥筝；n 表示數(shù)據(jù)規(guī)模的大小雏门；f(n) 表示每行代碼執(zhí)行的次數(shù)總和嘿歌。因為這是一個公式，所以用 f(n) 來表示茁影。公式中的 O宙帝，表示代碼的執(zhí)行時間 T(n) 與 f(n) 表達(dá)式成正比。
所以募闲，第一個例子中的 T(n) = O(2n+2)步脓，第二個例子中的 T(n) = O(2n2+2n+3)。這就是大 O 時間復(fù)雜度表示法浩螺。大 O 時間復(fù)雜度實(shí)際上并不具體表示代碼真正的執(zhí)行時間靴患，而是表示代碼執(zhí)行時間隨數(shù)據(jù)規(guī)模增長的變化趨勢，所以要出，也叫作漸進(jìn)時間復(fù)雜度（asymptotic time complexity）鸳君，簡稱時間復(fù)雜度。
當(dāng) n 很大時患蹂，你可以把它想象成 10000或颊、100000。而公式中的低階传于、常量囱挑、系數(shù)三部分并不左右增長趨勢，所以都可以忽略沼溜。我們只需要記錄一個最大量級就可以了平挑，如果用大 O 表示法表示剛講的那兩段代碼的時間復(fù)雜度，就可以記為：T(n) = O(n)盛末； T(n) = O(n2)弹惦。
時間復(fù)雜度分析
前面介紹了大 O 時間復(fù)雜度的由來和表示方法。現(xiàn)在我們來看下悄但，如何分析一段代碼的時間復(fù)雜度？我這兒有三個比較實(shí)用的方法可以分享給你石抡。
1. 只關(guān)注循環(huán)執(zhí)行次數(shù)最多的一段代碼
我剛才說了檐嚣，大 O 這種復(fù)雜度表示方法只是表示一種變化趨勢。我們通常會忽略掉公式中的常量、低階嚎京、系數(shù)嗡贺，只需要記錄一個最大階的量級就可以了。所以鞍帝，我們在分析一個算法诫睬、一段代碼的時間復(fù)雜度的時候，也只關(guān)注循環(huán)執(zhí)行次數(shù)最多的那一段代碼就可以了帕涌。這段核心代碼執(zhí)行次數(shù)的 n 的量級摄凡，就是整段要分析代碼的時間復(fù)雜度。
為了便于你理解蚓曼，我還拿前面的例子來說明亲澡。
1 int cal(int n) {
2 int sum = 0;
3 int i = 1;
4 for (; i <= n; ++i) {
5 sum = sum + i;
6 }
7 return sum;
8 }
其中第 2、3 行代碼都是常量級的執(zhí)行時間纫版，與 n 的大小無關(guān)床绪，所以對于復(fù)雜度并沒有影響。循環(huán)執(zhí)行次數(shù)最多的是第 4其弊、5 行代碼癞己，所以這塊代碼要重點(diǎn)分析。前面我們也講過梭伐，這兩行代碼被執(zhí)行了 n 次末秃，所以總的時間復(fù)雜度就是 O(n)。
2. 加法法則：總復(fù)雜度等于量級最大的那段代碼的復(fù)雜度
我這里還有一段代碼籽御。你可以先試著分析一下练慕，然后再往下看跟我的分析思路是否一樣。
int cal(int n) {
int sum_1 = 0;
int p = 1;
for (; p < 100; ++p) {
sum_1 = sum_1 + p;
}
int sum_2 = 0;
int q = 1;
for (; q < n; ++q) {
sum_2 = sum_2 + q;
}
int sum_3 = 0;
int i = 1;
int j = 1;
for (; i <= n; ++i) {
j = 1;
for (; j <= n; ++j) {
sum_3 = sum_3 + i * j;
}
}
return sum_1 + sum_2 + sum_3;
}
這個代碼分為三部分技掏，分別是求 sum_1铃将、sum_2、sum_3哑梳。我們可以分別分析每一部分的時間復(fù)雜度劲阎，然后把它們放到一塊兒，再取一個量級最大的作為整段代碼的復(fù)雜度鸠真。
第一段的時間復(fù)雜度是多少呢悯仙？這段代碼循環(huán)執(zhí)行了 100 次，所以是一個常量的執(zhí)行時間吠卷，跟 n 的規(guī)模無關(guān)锡垄。
這里我要再強(qiáng)調(diào)一下，即便這段代碼循環(huán) 10000 次祭隔、100000 次货岭，只要是一個已知的數(shù)，跟 n 無關(guān)，照樣也是常量級的執(zhí)行時間千贯。當(dāng) n 無限大的時候屯仗，就可以忽略。盡管對代碼的執(zhí)行時間會有很大影響搔谴，但是回到時間復(fù)雜度的概念來說魁袜，它表示的是一個算法執(zhí)行效率與數(shù)據(jù)規(guī)模增長的變化趨勢，所以不管常量的執(zhí)行時間多大敦第，我們都可以忽略掉峰弹。因為它本身對增長趨勢并沒有影響。
那第二段代碼和第三段代碼的時間復(fù)雜度是多少呢申尼？答案是 O(n) 和 O(n2)垮卓，你應(yīng)該能容易就分析出來，我就不啰嗦了师幕。
綜合這三段代碼的時間復(fù)雜度粟按，我們?nèi)∑渲凶畲蟮牧考墶Ｋ耘啵未a的時間復(fù)雜度就為 O(n2)灭将。也就是說：總的時間復(fù)雜度就等于量級最大的那段代碼的時間復(fù)雜度。那我們將這個規(guī)律抽象成公式就是：
如果 T1(n)=O(f(n))后控，T2(n)=O(g(n))庙曙；那么 T(n)=T1(n)+T2(n)=max(O(f(n)), O(g(n))) =O(max(f(n), g(n))).
3. 乘法法則：嵌套代碼的復(fù)雜度等于嵌套內(nèi)外代碼復(fù)雜度的乘積
我剛講了一個復(fù)雜度分析中的加法法則，這兒還有一個乘法法則浩淘。類比一下捌朴，你應(yīng)該能“猜到”公式是什么樣子的吧？
如果 T1(n)=O(f(n))张抄，T2(n)=O(g(n))砂蔽；那么 T(n)=T1(n)T2(n)=O(f(n))O(g(n))=O(f(n)*g(n)).
也就是說，假設(shè) T1(n) = O(n)署惯，T2(n) = O(n2)左驾，則 T1(n) * T2(n) = O(n3)。落實(shí)到具體的代碼上极谊，我們可以把乘法法則看成是嵌套循環(huán)诡右，我舉個例子給你解釋一下。
1int cal(int n) {
2 int ret = 0;
3 int i = 1;
4 for (; i < n; ++i) {
5 ret = ret + f(i);
6 }
7 }
8
9 int f(int n) {
10 int sum = 0;
11 int i = 1;
12 for (; i < n; ++i) {
13 sum = sum + i;
14 }
15 return sum;
16 }
我們單獨(dú)看 cal() 函數(shù)轻猖。假設(shè) f() 只是一個普通的操作帆吻，那第 4～6 行的時間復(fù)雜度就是，T1(n) = O(n)蜕依。但 f() 函數(shù)本身不是一個簡單的操作桅锄，它的時間復(fù)雜度是 T2(n) = O(n)琉雳，所以样眠，整個 cal() 函數(shù)的時間復(fù)雜度就是友瘤，T(n) = T1(n) * T2(n) = O(n*n) = O(n2)。
我剛剛講了三種復(fù)雜度的分析技巧檐束。不過辫秧，你并不用刻意去記憶。實(shí)際上被丧，復(fù)雜度分析這個東西關(guān)鍵在于“熟練”盟戏。你只要多看案例，多分析甥桂，就能做到“無招勝有招”柿究。
幾種常見時間復(fù)雜度實(shí)例分析
雖然代碼千差萬別，但是常見的復(fù)雜度量級并不多黄选。我稍微總結(jié)了一下蝇摸，這些復(fù)雜度量級幾乎涵蓋了你今后可以接觸的所有代碼的復(fù)雜度量級。
對于剛羅列的復(fù)雜度量級办陷，我們可以粗略地分為兩類貌夕，多項式量級和非多項式量級。其中民镜，非多項式量級只有兩個：O(2n) 和 O(n!)啡专。
我們把時間復(fù)雜度為非多項式量級的算法問題叫作NP（Non-Deterministic Polynomial，非確定多項式）問題制圈。
當(dāng)數(shù)據(jù)規(guī)模 n 越來越大時们童，非多項式量級算法的執(zhí)行時間會急劇增加，求解問題的執(zhí)行時間會無限增長鲸鹦。所以慧库，非多項式時間復(fù)雜度的算法其實(shí)是非常低效的算法。因此亥鬓，關(guān)于 NP 時間復(fù)雜度我就不展開講了完沪。我們主要來看幾種常見的多項式時間復(fù)雜度。
1. O(1)
首先你必須明確一個概念覆积，O(1) 只是常量級時間復(fù)雜度的一種表示方法，并不是指只執(zhí)行了一行代碼熟呛。比如這段代碼宽档，即便有 3 行，它的時間復(fù)雜度也是 O(1）庵朝，而不是 O(3)吗冤。
1 int i = 8;
2 int j = 6;
3 int sum = i + j;
我稍微總結(jié)一下又厉，只要代碼的執(zhí)行時間不隨 n 的增大而增長，這樣代碼的時間復(fù)雜度我們都記作 O(1)椎瘟「仓拢或者說，一般情況下肺蔚，只要算法中不存在循環(huán)語句煌妈、遞歸語句，即使有成千上萬行的代碼宣羊，其時間復(fù)雜度也是Ο(1)璧诵。
2. O(logn)、O(nlogn)
對數(shù)階時間復(fù)雜度非常常見仇冯，同時也是最難分析的一種時間復(fù)雜度之宿。我通過一個例子來說明一下。
1 i=1;
2 while (i <= n) {
3 i = i * 2;
4 }
根據(jù)我們前面講的復(fù)雜度分析方法苛坚，第三行代碼是循環(huán)執(zhí)行次數(shù)最多的比被。所以，我們只要能計算出這行代碼被執(zhí)行了多少次炕婶，就能知道整段代碼的時間復(fù)雜度姐赡。
從代碼中可以看出，變量 i 的值從 1 開始取柠掂，每循環(huán)一次就乘以 2项滑。當(dāng)大于 n 時，循環(huán)結(jié)束涯贞。還記得我們高中學(xué)過的等比數(shù)列嗎枪狂？實(shí)際上，變量 i 的取值就是一個等比數(shù)列宋渔。如果我把它一個一個列出來州疾，就應(yīng)該是這個樣子的：
所以，我們只要知道 x 值是多少皇拣，就知道這行代碼執(zhí)行的次數(shù)了严蓖。通過 2x=n 求解 x 這個問題我們想高中應(yīng)該就學(xué)過了，我就不多說了氧急。x=log2n颗胡，所以，這段代碼的時間復(fù)雜度就是 O(log2n)吩坝。
現(xiàn)在毒姨，我把代碼稍微改下，你再看看钉寝，這段代碼的時間復(fù)雜度是多少弧呐？
1 i=1;
2 while (i <= n) {
3 i = i * 3;
4 }
根據(jù)我剛剛講的思路闸迷，很簡單就能看出來，這段代碼的時間復(fù)雜度為 O(log3n)俘枫。
實(shí)際上腥沽，不管是以 2 為底、以 3 為底崩哩，還是以 10 為底巡球，我們可以把所有對數(shù)階的時間復(fù)雜度都記為 O(logn)言沐。為什么呢邓嘹？
我們知道，對數(shù)之間是可以互相轉(zhuǎn)換的险胰，log3n 就等于 log32 * log2n汹押，所以 O(log3n) = O(C * log2n)，其中 C=log32 是一個常量起便∨锛郑基于我們前面的一個理論：在采用大 O 標(biāo)記復(fù)雜度的時候，可以忽略系數(shù)榆综，即 O(Cf(n)) = O(f(n))妙痹。所以，O(log2n) 就等于 O(log3n)鼻疮。因此怯伊，在對數(shù)階時間復(fù)雜度的表示方法里，我們忽略對數(shù)的“底”判沟，統(tǒng)一表示為 O(logn)耿芹。
如果你理解了我前面講的 O(logn)，那 O(nlogn) 就很容易理解了挪哄。還記得我們剛講的乘法法則嗎吧秕？如果一段代碼的時間復(fù)雜度是 O(logn)，我們循環(huán)執(zhí)行 n 遍迹炼，時間復(fù)雜度就是 O(nlogn) 了砸彬。而且，O(nlogn) 也是一種非常常見的算法時間復(fù)雜度斯入。比如砂碉，歸并排序、快速排序的時間復(fù)雜度都是 O(nlogn)咱扣。
3. O(m+n)绽淘、O(m*n)
我們再來講一種跟前面都不一樣的時間復(fù)雜度，代碼的復(fù)雜度由兩個數(shù)據(jù)的規(guī)模來決定闹伪。老規(guī)矩沪铭，先看代碼壮池！
int cal(int m, int n) {
int sum_1 = 0;
int i = 1;
for (; i < m; ++i) {
sum_1 = sum_1 + i;
}
int sum_2 = 0;
int j = 1;
for (; j < n; ++j) {
sum_2 = sum_2 + j;
}
return sum_1 + sum_2;
}
從代碼中可以看出，m 和 n 是表示兩個數(shù)據(jù)規(guī)模杀怠。我們無法事先評估 m 和 n 誰的量級大椰憋，所以我們在表示復(fù)雜度的時候，就不能簡單地利用加法法則赔退，省略掉其中一個绑榴。所以，上面代碼的時間復(fù)雜度就是 O(m+n)酗洒。
針對這種情況但惶，原來的加法法則就不正確了，我們需要將加法規(guī)則改為：T1(m) + T2(n) = O(f(m) + g(n))漆枚。但是乘法法則繼續(xù)有效：T1(m)*T2(n) = O(f(m) * f(n))创译。
空間復(fù)雜度分析
前面，咱們花了很長時間講大 O 表示法和時間復(fù)雜度分析墙基，理解了前面講的內(nèi)容软族，空間復(fù)雜度分析方法學(xué)起來就非常簡單了。
前面我講過残制，時間復(fù)雜度的全稱是漸進(jìn)時間復(fù)雜度立砸，表示算法的執(zhí)行時間與數(shù)據(jù)規(guī)模之間的增長關(guān)系。類比一下初茶，空間復(fù)雜度全稱就是漸進(jìn)空間復(fù)雜度（asymptotic space complexity）颗祝，表示算法的存儲空間與數(shù)據(jù)規(guī)模之間的增長關(guān)系。
我還是拿具體的例子來給你說明纺蛆。（這段代碼有點(diǎn)“傻”吐葵，一般沒人會這么寫，我這么寫只是為了方便給你解釋桥氏。）
1void print(int n) {
2 int i = 0;
3 int[] a = new int[n];
4 for (i; i <n; ++i) {
5 a[i] = i * i;
6 }
7 for (i = n-1; i >= 0; --i) {
8 print out a[i]
9 }
10}
跟時間復(fù)雜度分析一樣温峭，我們可以看到，第 2 行代碼中字支，我們申請了一個空間存儲變量 i凤藏，但是它是常量階的，跟數(shù)據(jù)規(guī)模 n 沒有關(guān)系堕伪，所以我們可以忽略揖庄。第 3 行申請了一個大小為 n 的 int 類型數(shù)組，除此之外欠雌，剩下的代碼都沒有占用更多的空間蹄梢，所以整段代碼的空間復(fù)雜度就是 O(n)。
我們常見的空間復(fù)雜度就是 O(1)富俄、O(n)禁炒、O(n2 )而咆，像 O(logn)、O(nlogn) 這樣的對數(shù)階復(fù)雜度平時都用不到幕袱。而且暴备，空間復(fù)雜度分析比時間復(fù)雜度分析要簡單很多。所以们豌，對于空間復(fù)雜度涯捻，掌握剛我說的這些內(nèi)容已經(jīng)足夠了。
二望迎、淺析最好障癌、最壞、平均擂煞、均攤時間復(fù)雜度
上一節(jié)混弥，我們講了復(fù)雜度的大 O 表示法和幾個分析技巧，還舉了一些常見復(fù)雜度分析的例子对省，比如 O(1)、O(logn)晾捏、O(n)蒿涎、O(nlogn) 復(fù)雜度分析。掌握了這些內(nèi)容惦辛，對于復(fù)雜度分析這個知識點(diǎn)劳秋，你已經(jīng)可以到及格線了。但是胖齐，我想你肯定不會滿足于此玻淑。
今天我會繼續(xù)給你講四個復(fù)雜度分析方面的知識點(diǎn)，最好情況時間復(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)該可以看出來讼稚，這段代碼要實(shí)現(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ā)生的概率其實(shí)并不大。為了更好地表示平均情況下的復(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é)論雖然是正確的，但是計算過程稍微有點(diǎn)兒問題檬寂。究竟是什么問題呢终抽？我們剛講的這 n+1 種情況，出現(xiàn)的概率并不是一樣的。我?guī)憔唧w分析一下昼伴。（這里要稍微用到一點(diǎn)兒概率論的知識匾旭，不過非常簡單，你不用擔(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ā)生的概率考慮進(jìn)去耙蔑。如果我們把每種情況發(fā)生的概率也考慮進(jìn)去，那平均時間復(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í)際上，在大多數(shù)情況下溢豆，我們并不需要區(qū)分最好蜒简、最壞、平均情況時間復(fù)雜度三種情況沫换。像我們上一節(jié)課舉的那些例子那樣臭蚁，很多時候最铁，我們使用一個復(fù)雜度就可以滿足需求了。只有同一塊代碼在不同的情況下垮兑，時間復(fù)雜度有量級的差距冷尉，我們才會使用這三種復(fù)雜度表示法來區(qū)分。
均攤時間復(fù)雜度
到此為止系枪，你應(yīng)該已經(jīng)掌握了算法復(fù)雜度分析的大部分內(nèi)容了雀哨。下面我要給你講一個更加高級的概念，均攤時間復(fù)雜度私爷，以及它對應(yīng)的分析方法雾棺，攤還分析（或者叫平攤分析）。
均攤時間復(fù)雜度衬浑，聽起來跟平均時間復(fù)雜度有點(diǎn)兒像捌浩。對于初學(xué)者來說，這兩個概念確實(shí)非常容易弄混工秩。我前面說了尸饺，大部分情況下，我們并不需要區(qū)分最好助币、最壞浪听、平均三種復(fù)雜度。平均復(fù)雜度只在某些特殊情況下才會用到眉菱，而均攤時間復(fù)雜度應(yīng)用的場景比它更加特殊迹栓、更加有限。
老規(guī)矩俭缓，我還是借助一個具體的例子來幫助你理解克伊。（當(dāng)然，這個例子只是我為了方便講解想出來的华坦，實(shí)際上沒人會這么寫答毫。）
// 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;
}
我先來解釋一下這段代碼。這段代碼實(shí)現(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ù)雜度分析其實(shí)并不需要這么復(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)進(jìn)行一組連續(xù)操作中次屠，大部分情況下時間復(fù)雜度都很低园匹，只有個別情況下時間復(fù)雜度比較高，而且這些操作之間存在前后連貫的時序關(guān)系劫灶，這個時候裸违，我們就可以將這一組操作放在一塊兒分析，看是否能將較高時間復(fù)雜度那次操作的耗時本昏，平攤到其他那些時間復(fù)雜度比較低的操作上供汛。而且，在能夠應(yīng)用均攤時間復(fù)雜度分析的場合涌穆，一般均攤時間復(fù)雜度就等于最好情況時間復(fù)雜度怔昨。
盡管很多數(shù)據(jù)結(jié)構(gòu)和算法書籍都花了很大力氣來區(qū)分平均時間復(fù)雜度和均攤時間復(fù)雜度，但其實(shí)我個人認(rèn)為宿稀，均攤時間復(fù)雜度就是一種特殊的平均時間復(fù)雜度趁舀，我們沒必要花太多精力去區(qū)分它們。你最應(yīng)該掌握的是它的分析方法祝沸，攤還分析矮烹。至于分析出來的結(jié)果是叫平均還是叫均攤，這只是個說法罩锐，并不重要奉狈。
