程序 = 數(shù)據(jù)結(jié)構(gòu) + 算法

作者 謝恩銘硕蛹，公眾號(hào)「程序員聯(lián)盟」（微信號(hào)：coderhub）泽论。
轉(zhuǎn)載請(qǐng)注明出處。
原文：http://www.reibang.com/p/3e5e987c7e05

《數(shù)據(jù)結(jié)構(gòu)和算法》全系列

內(nèi)容簡(jiǎn)介

1. 大 O 符號(hào)
2. 時(shí)間復(fù)雜度和空間復(fù)雜度
3. 最壞情況下的復(fù)雜度
4. 第一部分第五課預(yù)告

1. 大 O 符號(hào)

上一課 數(shù)據(jù)結(jié)構(gòu)和算法 | 第一部分第三課：算法復(fù)雜度（上） 我們開始了算法復(fù)雜度的學(xué)習(xí)，這一課我們繼續(xù)學(xué)習(xí)后半段。

我們已經(jīng)看到侦香，復(fù)雜度只考慮操作數(shù)目的一個(gè)數(shù)量級(jí)（忽略了其他的組分）慕匠，這是一種近似袱吆。

為了表示這種近似，我們使用一個(gè)特定的符號(hào)盛霎，就是著名的 大 O 符號(hào)污朽。

大 O 符號(hào)（Big O notation）散吵，又稱為漸進(jìn)符號(hào)，是用于描述函數(shù)漸近行為的數(shù)學(xué)符號(hào)蟆肆。更確切地說矾睦，它是用另一個(gè)（通常更簡(jiǎn)單的）函數(shù)來描述一個(gè)函數(shù)數(shù)量級(jí)的漸近上界。
在數(shù)學(xué)中颓芭，它一般用來刻畫被截?cái)嗟臒o窮級(jí)數(shù)尤其是漸近級(jí)數(shù)的剩余項(xiàng)顷锰。
在計(jì)算機(jī)科學(xué)中，它在分析算法復(fù)雜度的方面非常有用亡问。
大 O 符號(hào)是由德國數(shù)論學(xué)家 保羅·巴赫曼（Paul Bachmann）在其 1892 年的著作《解析數(shù)論》（Analytische Zahlentheorie）首先引入的官紫。而這個(gè)記號(hào)則是在另一位德國數(shù)論學(xué)家 艾德蒙·朗道（Edmund Landau）的著作中才推廣的肛宋，因此它有時(shí)又稱為 朗道符號(hào)（Landau Notation）。
代表“order of ...”（…階）的大 O束世，最初是一個(gè)大寫希臘字母“Ο”（Omicron）酝陈，現(xiàn)今用的是大寫拉丁字母“O”。
-- 摘自 百度百科

例如毁涉，小鴨子們?nèi)ザ燃龠@個(gè)故事里沉帮，農(nóng)夫 Oscar 的第一種算法有 N² 個(gè)操作，我們就說此算法的復(fù)雜度是 O(N²)贫堰。類似地穆壕，第二種更快的算法的復(fù)雜度是 O(N)。

大 O 符號(hào)有點(diǎn)像一個(gè)大圓形的袋子其屏，可以把不同的操作數(shù)目整合在一起喇勋，使之具有一個(gè)同樣的數(shù)量級(jí)。

例如偎行，如果有三個(gè)算法川背，它們的操作數(shù)目分別為 N，5N + 7 和 N / 4蛤袒，我們就都用 O(N) （讀作 “N 的 大 O”熄云。當(dāng)然了，讀法其實(shí)不是那么固定）來表示這三個(gè)算法的復(fù)雜度妙真。

類似地缴允，如果一個(gè)算法的操作數(shù)是（2 * N² + 5 * N + 7），那么它的復(fù)雜度是 O(N²)：我們忽略了 5 * N 和 7 這兩項(xiàng)隐孽，因?yàn)樗鼈兣c 2N² 相比數(shù)量級(jí)較小癌椿。隨著 N 的增大，這兩項(xiàng)的增長速率比 2N² 要慢菱阵，因此我們保留 2N² 即可踢俄，又因?yàn)槌?shù)乘法因子（這里是 2）不予考慮，因此記為 O(N²)晴及。

我們說 f(N) 表示“N 的函數(shù)”（例如都办， f(N) = 2 * N² + 5 * N + 7) ），那么 O(f(N)) 表示的是“大約有 f(N) 個(gè)操作的算法的復(fù)雜度”虑稼，這里的“大約”是非常關(guān)鍵的琳钉。

2. 時(shí)間復(fù)雜度和空間復(fù)雜度

下面我們來學(xué)習(xí)算法中常聽到的“時(shí)間復(fù)雜度”和“空間復(fù)雜度”。

為什么我竟然想到了漫威里面的大反派滅霸的無限手套呢蛛倦？上面有時(shí)間寶石和空間寶石這兩顆無限寶石歌懒。
一定是因?yàn)槲铱戳恕稄?fù)仇者聯(lián)盟3：無限戰(zhàn)爭(zhēng)》和《復(fù)仇者聯(lián)盟4：終局之戰(zhàn)》的關(guān)系...

滅霸的無限手套上的六顆無限寶石

那么“時(shí)間復(fù)雜度”和“空間復(fù)雜度”這一對(duì)“活寶”到底是啥意思呢？且聽我慢慢道來溯壶。

“在很久很久以前及皂，宇宙中有 6 顆無限寶石甫男，分別是時(shí)間寶石、空間寶石...”

讀者：“小編验烧，你快醒醒板驳，講正經(jīng)的！”
我：“好碍拆，好若治，講正經(jīng)的，講正經(jīng)的～”

為了盡可能精確地表達(dá)算法的復(fù)雜度感混，我們可以做很多選擇端幼。

首先，我們選擇輸入條件的量化弧满，例如通過變量 N（N 行 N 列小鴨子静暂，N 個(gè)學(xué)生，N 架飛機(jī)谱秽，等）。當(dāng)然了摹迷，不一定要用 N 這個(gè)變量名疟赊，我們可以選擇其他變量名（比如 M，Z峡碉，X近哟，Y 等），但更重要的是我們也可以不止用一個(gè)變量鲫寄。

例如吉执，如果我們的問題是要在一張紙上畫畫，那么我們可能會(huì)將算法的復(fù)雜度表達(dá)為畫紙的長度 L 和寬度 W 的函數(shù)地来。同樣地戳玫，如果農(nóng)夫 Oscar 擁有比可用的池塘數(shù)目更多的小鴨子的行數(shù)，那么他可以將算法的復(fù)雜度表達(dá)為小鴨子的行數(shù) N 和池塘數(shù) P 的函數(shù)未斑。

另一個(gè)重要的選擇是要度量的操作的類型咕宿。到目前為止，我們其實(shí)只談?wù)摿怂惴ǖ男驶蛐阅埽ň褪撬惴觳豢欤├唷５歉В绦騿T不僅對(duì)算法的執(zhí)行時(shí)間感興趣，他們也可能會(huì)度量許多其他特性芽突，最常見的是內(nèi)存消耗（Memory Consumption）试浙。

算法的內(nèi)存消耗也是度量算法復(fù)雜度的標(biāo)準(zhǔn)。例如寞蚌，如果需要為一個(gè)輸入大小為 N 的算法分配 N 千字節(jié)（KiloByte田巴，千字節(jié)钠糊，簡(jiǎn)稱 KB。其實(shí)是 1024 個(gè)字節(jié)）的內(nèi)存固额，則此算法的內(nèi)存復(fù)雜度可以表示為 O(N)眠蚂。

內(nèi)存復(fù)雜度是和算法的內(nèi)存消耗有關(guān)的復(fù)雜度，度量的并不是算法的效率斗躏，而是消耗/占用的內(nèi)存空間大小逝慧，因此我們把它稱為算法的空間復(fù)雜度（Space Complexity）。相對(duì)的啄糙，之前我們討論的對(duì)于算法的執(zhí)行速度（快不快）的度量是用的時(shí)間復(fù)雜度（Time Complexity）笛臣。

空間復(fù)雜度是對(duì)一個(gè)算法在運(yùn)行過程中臨時(shí)占用存儲(chǔ)空間大小的度量，記做 S(N) = O(f(N))隧饼。

相對(duì)的沈堡，算法的時(shí)間復(fù)雜度就記為 T(N) = O(f(N))。
因?yàn)?S 是 Space（空間）的首字母燕雁，T 是 Time（時(shí)間）的首字母诞丽。

在計(jì)算算法的空間復(fù)雜度的時(shí)候，我們其實(shí)也不知道算法所消耗/占用的具體的內(nèi)存大泄崭瘛（內(nèi)存是以字節(jié)（Byte）為單位）僧免，我們計(jì)算的是算法所使用的（數(shù)據(jù)）結(jié)構(gòu)的數(shù)量級(jí)。

比如說你使用 N 個(gè)大小為 N 的數(shù)組捏浊，那么其空間復(fù)雜度為 O(N²)懂衩。

例如，對(duì)于小鴨子們?nèi)ザ燃俚哪莻€(gè)故事金踪，可能農(nóng)夫 Oscar 給他的每只小鴨子都起了一個(gè)英文名字浊洞。他隨身攜帶著一份小鴨子的名字的表單，以免自己忘記胡岔。

小鴨子的名字表單

上面的表格是農(nóng)夫 Oscar 用來記錄小鴨子們的名字的表單的一個(gè)直觀的表示：一共有 5 個(gè)名字（HARRY法希，JAMES，HENRY姐军，EMILY铁材，ALICE），分別對(duì)應(yīng) 5 只小鴨子奕锌。表格里的每一行儲(chǔ)存一個(gè)名字著觉，每一行有 5 個(gè)格子（類似于數(shù)組的 5 個(gè)元素），5 x 5 = 25 個(gè)格子惊暴，一個(gè)格子里是一個(gè)英文字符饼丘。

如果聯(lián)系到計(jì)算機(jī)的內(nèi)存層面，N 只小鴨子需要 N 個(gè)數(shù)組來保存它們的名字辽话，每個(gè)數(shù)組里是一只小鴨子的名字（都是英文字符）肄鸽，而數(shù)組的大形啦　（這里是字符數(shù)）都統(tǒng)一為 N。所以這里的空間復(fù)雜度為 O(N²)典徘。

有些時(shí)候蟀苛，我們需要同時(shí)考慮算法的時(shí)間復(fù)雜度（執(zhí)行速度）和空間復(fù)雜度（執(zhí)行期間占用的內(nèi)存空間的大小）逮诲。

一般在比較簡(jiǎn)單的情況下帜平，我們對(duì)算法的空間復(fù)雜度沒有那么關(guān)注。但對(duì)于更復(fù)雜的問題梅鹦，算法的空間復(fù)雜度也許會(huì)引起更多的重視：例如裆甩，我們也許會(huì)通過犧牲一點(diǎn)執(zhí)行速度來使用更少的內(nèi)存；或者甚至通過增加算法的空間復(fù)雜度來提高執(zhí)行速度齐唆，例如通過在表中存儲(chǔ)已經(jīng)計(jì)算好的結(jié)果（緩存（cache）的原理）嗤栓。

對(duì)程序的約束越多，所需的信息就越精確箍邮。在計(jì)算機(jī)科學(xué)的某些領(lǐng)域茉帅，我們也會(huì)對(duì)算法的其他特征感興趣。而這些特征中的某些也可以用算法的某種復(fù)雜度來度量锭弊。例如担敌，大型計(jì)算機(jī)或嵌入式系統(tǒng)的程序員可能會(huì)考慮算法的功耗，以節(jié)省電量廷蓉。

然而，在一般情況下马昙，我們只關(guān)注算法的時(shí)間復(fù)雜度和空間復(fù)雜度桃犬，甚至主要關(guān)注時(shí)間復(fù)雜度。

3. 最壞情況下的復(fù)雜度

正如我們之前所說行楞，算法執(zhí)行的操作數(shù)目很明顯取決于起始條件攒暇。

例如，下面是一個(gè)非常簡(jiǎn)單的算法子房，用于獲知一個(gè)給定的值是否在值列表中（例如形用，“我是否已將雞蛋加入我的購物清單？”）：

為了獲知一個(gè)給定的值是否在值列表中证杭，我們可以這么做：
遍歷整個(gè)列表田度，在找到給定值的時(shí)候即可停下，表示值在列表中解愤；
如果我們已經(jīng)遍歷完整個(gè)列表镇饺，仍然沒有找到給定值，那么說明給定的值不在值列表中送讲。

想象一下奸笤，如果我們要查找的值不在列表中惋啃，并且列表里有 L 個(gè)元素。那么要確定這個(gè)值是否存在监右，算法就必須遍歷一遍整個(gè)列表边灭，將每個(gè)值與要查找的值進(jìn)行比較，那將需要進(jìn)行 L 次比較健盒。因此绒瘦，我們可以說算法具有 O(L) 的復(fù)雜度（很明顯，這里考慮的是時(shí)間復(fù)雜度）味榛。我們也可以說椭坚，此算法的時(shí)間復(fù)雜度是呈線性的（如果我們將輸入列表的大小加倍，那么此算法將花費(fèi)兩倍的時(shí)間）搏色。

但是善茎，如果要查找的值位于列表的最開頭，會(huì)怎么樣呢频轿？

例如垂涯，如果“雞蛋”是我們的購物清單中的第一個(gè)元素，它會(huì)立即被注意到航邢，我們將僅在進(jìn)行一次操作后就停止遍歷耕赘。在其他情況下，即使列表包含 3000 個(gè)元素膳殷，可能我們的搜索工作也會(huì)在 4 到 5 次操作后停止操骡。

這就是 “最壞情況”（Worst Case）的概念發(fā)揮作用的地方：在計(jì)算算法的復(fù)雜度時(shí)，可以認(rèn)為給定的輸入對(duì)于我們的算法來說是處于“最壞的情況”赚窃。我們將計(jì)算需要最多操作（而不僅僅是一個(gè)或兩個(gè)）的輸入情況下的操作數(shù)册招，例如給定值不在列表里的情況。

從程序員的角度來看勒极，這是一種安全性：計(jì)算出的復(fù)雜度處于“最壞情況”是掰，因此他知道算法的表現(xiàn)只會(huì)更好。

就像網(wǎng)絡(luò)安全領(lǐng)域的程序員會(huì)通過自問“最心懷惡意的用戶可能會(huì)通過輸入什么文本來入侵我的網(wǎng)站辱匿？”這樣的問題來敦促自己提升應(yīng)用程序的安全性一樣键痛，專注于算法研究的人也想知道“到底是算法中的哪個(gè)元素花了我的算法的大部分時(shí)間？”

這種方法可以度量所謂的“最壞情況下的復(fù)雜度”匾七。

在本教程中絮短，除非明確指出，我們只考慮算法在最壞情況下的復(fù)雜度昨忆。

4. 第一部分第五課預(yù)告

終于把算法復(fù)雜度講解得差不多了戚丸，真是不容易。大家也辛苦了。

今天的課就到這里限府，一起加油吧夺颤！

下一課：數(shù)據(jù)結(jié)構(gòu)和算法 | 第一部分第五課：算法復(fù)雜度實(shí)踐

我是 謝恩銘，公眾號(hào)「程序員聯(lián)盟」（微信號(hào)：coderhub）運(yùn)營者胁勺，慕課網(wǎng)精英講師 Oscar 老師世澜，終生學(xué)習(xí)者。
熱愛生活署穗，喜歡游泳寥裂，略懂烹飪。
人生格言：「向著標(biāo)桿直跑」