大 O 復(fù)雜度表示法
算法的執(zhí)行效率附井，粗略地講，就是算法代碼執(zhí)行的時間人弓。但是，如何在不運行代碼的情況下节猿，用 “ 肉眼 ” 得到一段代碼的執(zhí)行時間呢票从？
這里有段非常簡單的代碼，求 1,2,3…n 的累加和”踔觯現(xiàn)在峰鄙，我就帶你一塊來估算一下這段代碼的執(zhí)行時間。
int cal(int n) {
int sum = 0;
int i = 1;
for (; i <= n; ++i) {
sum = sum + i;
}
return sum;
03|復(fù)雜度分析（上）：如何分析太雨、統(tǒng)計算法的執(zhí)行效率和資源消耗吟榴？
file:///F/temp/geektime/數(shù)據(jù)結(jié)構(gòu)與算法之美/03復(fù)雜度分析（上）：如何分析囊扳、統(tǒng)計算法的執(zhí)行效率和資源消耗吩翻？
}
從CPU的角度來看，這段代碼的每一行都執(zhí)行著類似的操作：讀數(shù)據(jù)-運算-寫數(shù)據(jù)锥咸。盡管每行代碼對應(yīng)的CPU執(zhí)行的個數(shù)狭瞎、執(zhí)行的時間都不一樣，但是搏予，我們這里
只是粗略估計熊锭，所以可以假設(shè)每行代碼執(zhí)行的時間都一樣，為 unit_time 雪侥。在這個假設(shè)的基礎(chǔ)之上碗殷，這段代碼的總執(zhí)行時間是多少呢？
第 2 速缨、 3 行代碼分別需要 1 個 unit_time 的執(zhí)行時間专钉，第 4 荤傲、 5 行都運行了 n 遍断部，所以需要 2n*unit_time 的執(zhí)行時間呢燥，所以這段代碼總的執(zhí)行時間就是 (2n+2)*unit_time ∫眨可
以看出來牍陌，所有代碼的執(zhí)行時間T(n)與每行代碼的執(zhí)行次數(shù)成正比。
按照這個分析思路员咽，我們再來看這段代碼。
int cal(int n) {
int sum = 0;
int i = 1;
int j = 1;
for (; i <= n; ++i) {
j = 1;
for (; j <= n; ++j) {
sum = sum + i * j;
}
}
}
我們依舊假設(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í)行了n 2 遍绘搞，所以需
要2n 2 * unit_time的執(zhí)行時間彤避。所以，整段代碼總的執(zhí)行時間T(n) = (2n 2 +2n+3)*unit_time夯辖。
盡管我們不知道unit_time的具體值琉预，但是通過這兩段代碼執(zhí)行時間的推導(dǎo)過程，我們可以得到一個非常重要的規(guī)律蒿褂，那就是圆米，所有代碼的執(zhí)行時間T(n)與每行代碼
的執(zhí)行次數(shù)n成正比。
我們可以把這個規(guī)律總結(jié)成一個公式啄栓。注意娄帖，大 O 就要登場了！
T(n)=O(f(n))
我來具體解釋一下這個公式昙楚。其中近速， T(n) 我們已經(jīng)講過了，它表示代碼執(zhí)行的時間桂肌； n 表示數(shù)據(jù)規(guī)模的大惺浮； f(n) 表示每行代碼執(zhí)行的次數(shù)總和崎场。因為這是一個公
式佩耳，所以用 f(n) 來表示。公式中的 O 谭跨，表示代碼的執(zhí)行時間 T(n) 與 f(n) 表達式成正比干厚。
所以，第一個例子中的T(n) = O(2n+2)螃宙，第二個例子中的T(n) = O(2n 2 +2n+3)蛮瞄。這就是大O時間復(fù)雜度表示法。大O時間復(fù)雜度實際上并不具體表示代碼真正的執(zhí)行
時間谆扎，而是表示代碼執(zhí)行時間隨數(shù)據(jù)規(guī)模增長的變化趨勢挂捅，所以，也叫作漸進時間復(fù)雜度（asymptotic time complexity）堂湖，簡稱時間復(fù)雜度闲先。
當(dāng) n 很大時状土，你可以把它想象成 10000 、 100000 伺糠。而公式中的低階蒙谓、常量、系數(shù)三部分并不左右增長趨勢训桶，所以都可以忽略累驮。我們只需要記錄一個最大量級就可以
了，如果用大O表示法表示剛講的那兩段代碼的時間復(fù)雜度舵揭，就可以記為：T(n) = O(n)谤专； T(n) = O(n 2 )。
時間復(fù)雜度分析
03|復(fù)雜度分析（上）：如何分析琉朽、統(tǒng)計算法的執(zhí)行效率和資源消耗毒租？
file:///F/temp/geektime/數(shù)據(jù)結(jié)構(gòu)與算法之美/03復(fù)雜度分析（上）：如何分析、統(tǒng)計算法的執(zhí)行效率和資源消耗箱叁？.html[2019/1/15 15:35:11]
前面介紹了大 O 時間復(fù)雜度的由來和表示方法∈澹現(xiàn)在我們來看下，如何分析一段代碼的時間復(fù)雜度耕漱？我這兒有三個比較實用的方法可以分享給你算色。
1.只關(guān)注循環(huán)執(zhí)行次數(shù)最多的一段代碼
我剛才說了，大O這種復(fù)雜度表示方法只是表示一種變化趨勢螟够。我們通常會忽略掉公式中的常量灾梦、低階、系數(shù)妓笙，只需要記錄一個最大階的量級就可以了若河。所以，我
們在分析一個算法寞宫、一段代碼的時間復(fù)雜度的時候萧福，也只關(guān)注循環(huán)執(zhí)行次數(shù)最多的那一段代碼就可以了。這段核心代碼執(zhí)行次數(shù)的n的量級辈赋，就是整段要分析代碼
的時間復(fù)雜度鲫忍。
為了便于你理解，我還拿前面的例子來說明钥屈。
int cal(int n) {
int sum = 0;
int i = 1;
for (; i <= n; ++i) {
sum = sum + i;
}
return sum;
}
其中第 2 悟民、 3 行代碼都是常量級的執(zhí)行時間，與 n 的大小無關(guān)篷就，所以對于復(fù)雜度并沒有影響射亏。循環(huán)執(zhí)行次數(shù)最多的是第 4 、 5 行代碼，所以這塊代碼要重點分析鸦泳。前面
我們也講過银锻，這兩行代碼被執(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)捷兰。
03|復(fù)雜度分析（上）：如何分析立叛、統(tǒng)計算法的執(zhí)行效率和資源消耗？
file:///F/temp/geektime/數(shù)據(jù)結(jié)構(gòu)與算法之美/03復(fù)雜度分析（上）：如何分析贡茅、統(tǒng)計算法的執(zhí)行效率和資源消耗秘蛇？.html[2019/1/15 15:35:11]
這里我要再強調(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(n 2 )，你應(yīng)該能容易就分析出來，我就不啰嗦了赎懦。
綜合這三段代碼的時間復(fù)雜度雀鹃，我們?nèi)∑渲凶畲蟮牧考墶Ｋ岳剑未a的時間復(fù)雜度就為O(n 2 )黎茎。也就是說：總的時間復(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(n 2 )屏积，則T1(n) * T2(n) = O(n 3 )。落實到具體的代碼上伸但，我們可以把乘法法則看成是嵌套循環(huán)肾请，我舉個例子給你解釋一下。
int cal(int n) {
int ret = 0;
int i = 1;
for (; i < n; ++i) {
ret = ret + f(i);
}
}
int f(int n) {
int sum = 0;
int i = 1;
for (; i < n; ++i) {
sum = sum + i;
}
return sum;
}
我們單獨看 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(n 2 )。
我剛剛講了三種復(fù)雜度的分析技巧捞烟。不過薄声，你并不用刻意去記憶。實際上题画，復(fù)雜度分析這個東西關(guān)鍵在于 “ 熟練 ” 默辨。你只要多看案例，多分析苍息，就能做到 “ 無招勝有
招 ” 缩幸。
幾種常見時間復(fù)雜度實例分析
雖然代碼千差萬別壹置，但是常見的復(fù)雜度量級并不多。我稍微總結(jié)了一下表谊，這些復(fù)雜度量級幾乎涵蓋了你今后可以接觸的所有代碼的復(fù)雜度量級钞护。
03|復(fù)雜度分析（上）：如何分析、統(tǒng)計算法的執(zhí)行效率和資源消耗爆办？
file:///F/temp/geektime/數(shù)據(jù)結(jié)構(gòu)與算法之美/03復(fù)雜度分析（上）：如何分析难咕、統(tǒng)計算法的執(zhí)行效率和資源消耗？.html[2019/1/15 15:35:11]
對于剛羅列的復(fù)雜度量級押逼，我們可以粗略地分為兩類步藕，多項式量級和非多項式量級。其中挑格，非多項式量級只有兩個：O(2 n )和O(n!)。
當(dāng)數(shù)據(jù)規(guī)模 n 越來越大時沾歪，非多項式量級算法的執(zhí)行時間會急劇增加漂彤，求解問題的執(zhí)行時間會無限增長。所以灾搏，非多項式時間復(fù)雜度的算法其實是非常低效的算
法挫望。因此，關(guān)于NP時間復(fù)雜度我就不展開講了狂窑。我們主要來看幾種常見的多項式時間復(fù)雜度媳板。
1. O(1)
首先你必須明確一個概念， O(1) 只是常量級時間復(fù)雜度的一種表示方法泉哈，并不是指只執(zhí)行了一行代碼蛉幸。比如這段代碼，即便有 3 行丛晦，它的時間復(fù)雜度也是 O(1 ）奕纫，
而不是 O(3) 。
int i = 8;
int j = 6;
int sum = i + j;
03|復(fù)雜度分析（上）：如何分析烫沙、統(tǒng)計算法的執(zhí)行效率和資源消耗匹层？
file:///F/temp/geektime/數(shù)據(jù)結(jié)構(gòu)與算法之美/03復(fù)雜度分析（上）：如何分析、統(tǒng)計算法的執(zhí)行效率和資源消耗锌蓄？.
我稍微總結(jié)一下升筏，只要代碼的執(zhí)行時間不隨n的增大而增長，這樣代碼的時間復(fù)雜度我們都記作O(1)瘸爽∧茫或者說，一般情況下蝶糯，只要算法中不存在循環(huán)語句洋只、遞歸語
句辆沦，即使有成千上萬行的代碼，其時間復(fù)雜度也是Ο(1)识虚。
2. O(logn)肢扯、O(nlogn)
對數(shù)階時間復(fù)雜度非常常見，同時也是最難分析的一種時間復(fù)雜度担锤。我通過一個例子來說明一下蔚晨。
i=1;
while (i <= n) {
i = i * 2;
}
根據(jù)我們前面講的復(fù)雜度分析方法，第三行代碼是循環(huán)執(zhí)行次數(shù)最多的肛循。所以铭腕，我們只要能計算出這行代碼被執(zhí)行了多少次，就能知道整段代碼的時間復(fù)雜度多糠。
從代碼中可以看出累舷，變量 i 的值從 1 開始取，每循環(huán)一次就乘以 2 夹孔。當(dāng)大于 n 時被盈，循環(huán)結(jié)束。還記得我們高中學(xué)過的等比數(shù)列嗎搭伤？實際上只怎，變量 i 的取值就是一個等比
數(shù)列。如果我把它一個一個列出來怜俐，就應(yīng)該是這個樣子的：
所以身堡，我們只要知道x值是多少，就知道這行代碼執(zhí)行的次數(shù)了拍鲤。通過2 x =n求解x這個問題我們想高中應(yīng)該就學(xué)過了贴谎，我就不多說了。x=log 2 n殿漠，所以赴精，這段代碼的
時間復(fù)雜度就是O(log 2 n)。
現(xiàn)在绞幌，我把代碼稍微改下蕾哟，你再看看，這段代碼的時間復(fù)雜度是多少莲蜘？
i=1;
while (i <= n) {
i = i * 3;
}
根據(jù)我剛剛講的思路谭确，很簡單就能看出來，這段代碼的時間復(fù)雜度為O(log 3 n)票渠。
實際上逐哈，不管是以 2 為底、以 3 為底问顷，還是以 10 為底昂秃，我們可以把所有對數(shù)階的時間復(fù)雜度都記為 O(logn) 禀梳。為什么呢？
我們知道肠骆，對數(shù)之間是可以互相轉(zhuǎn)換的算途，log 3 n就等于log 3 2 * log 2 n，所以O(shè)(log 3 n) = O(C * log 2 n)蚀腿，其中C=log 3 2是一個常量嘴瓤。基于我們前面的一個理論：在采用
大O標(biāo)記復(fù)雜度的時候莉钙，可以忽略系數(shù)廓脆，即O(Cf(n)) = O(f(n))。所以磁玉，O(log 2 n) 就等于O(log 3 n)停忿。因此，在對數(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)
03|復(fù)雜度分析（上）：如何分析龙填、統(tǒng)計算法的執(zhí)行效率和資源消耗？
file:///F/temp/geektime/數(shù)據(jù)結(jié)構(gòu)與算法之美/03復(fù)雜度分析（上）：如何分析拐叉、統(tǒng)計算法的執(zhí)行效率和資源消耗岩遗？.html[2019/1/15 15:35:11]
我們再來講一種跟前面都不一樣的時間復(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ù)雜度的全稱是漸進時間復(fù)雜度颜武，表示算法的執(zhí)行時間與數(shù)據(jù)規(guī)模之間的增長關(guān)系。類比一下拖吼，空間復(fù)雜度全稱就是漸進空間復(fù)雜
度（asymptotic space complexity）鳞上，表示算法的存儲空間與數(shù)據(jù)規(guī)模之間的增長關(guān)系。
我還是拿具體的例子來給你說明吊档。（這段代碼有點 “ 傻 ” 篙议，一般沒人會這么寫，我這么寫只是為了方便給你解釋怠硼。）
void print(int n) {
int i = 0;
int[] a = new int[n];
for (i; i <n; ++i) {
a[i] = i * i;
}
for (i = n-1; i >= 0; --i) {
print out a[i]
}
}
跟時間復(fù)雜度分析一樣鬼贱，我們可以看到，第 2 行代碼中香璃，我們申請了一個空間存儲變量 i 这难，但是它是常量階的，跟數(shù)據(jù)規(guī)模 n 沒有關(guān)系葡秒，所以我們可以忽略姻乓。第 3 行申
請了一個大小為 n 的 int 類型數(shù)組，除此之外同云，剩下的代碼都沒有占用更多的空間糖权，所以整段代碼的空間復(fù)雜度就是 O(n) 。
我們常見的空間復(fù)雜度就是O(1)炸站、O(n)星澳、O(n 2 )，像O(logn)旱易、O(nlogn)這樣的對數(shù)階復(fù)雜度平時都用不到禁偎。而且腿堤，空間復(fù)雜度分析比時間復(fù)雜度分析要簡單很多。
所以如暖，對于空間復(fù)雜度笆檀，掌握剛我說的這些內(nèi)容已經(jīng)足夠了。
內(nèi)容小結(jié)
03|復(fù)雜度分析（上）：如何分析盒至、統(tǒng)計算法的執(zhí)行效率和資源消耗酗洒？
file:///F/temp/geektime/數(shù)據(jù)結(jié)構(gòu)與算法之美/03復(fù)雜度分析（上）：如何分析、統(tǒng)計算法的執(zhí)行效率和資源消耗枷遂？
基礎(chǔ)復(fù)雜度分析的知識到此就講完了樱衷，我們來總結(jié)一下。
復(fù)雜度也叫漸進復(fù)雜度酒唉，包括時間復(fù)雜度和空間復(fù)雜度矩桂，用來分析算法執(zhí)行效率與數(shù)據(jù)規(guī)模之間的增長關(guān)系，可以粗略地表示痪伦，越高階復(fù)雜度的算法侄榴，執(zhí)行效率
越低。常見的復(fù)雜度并不多网沾，從低階到高階有：O(1)癞蚕、O(logn)、O(n)辉哥、O(nlogn)涣达、O(n 2 )。等你學(xué)完整個專欄之后证薇，你就會發(fā)現(xiàn)幾乎所有的數(shù)據(jù)結(jié)構(gòu)和算法的復(fù)雜
度都跑不出這幾個。
復(fù)雜度分析并不難匆篓，關(guān)鍵在于多練浑度。 之后講后面的內(nèi)容時，我還會帶你詳細(xì)地分析每一種數(shù)據(jù)結(jié)構(gòu)和算法的時間鸦概、空間復(fù)雜度箩张。只要跟著我的思路學(xué)習(xí)、練習(xí)窗市，
你很快就能和我一樣先慷，每次看到代碼的時候，簡單的一眼就能看出其復(fù)雜度咨察，難的稍微分析一下就能得出答案
