作者 謝恩銘，公眾號「程序員聯(lián)盟」（微信號：coderhub）钳吟。
轉(zhuǎn)載請注明出處。
原文：http://www.reibang.com/p/14982c42b2d8
內(nèi)容簡介
- 算法的正確性
- 算法的復(fù)雜度
- “漸近”度量
- 第一部分第四課預(yù)告
1. 算法的正確性
上一課 數(shù)據(jù)結(jié)構(gòu)和算法 | 第一部分第二課：小鴨子們?nèi)ヂ眯?/a> 中窘拯，我們講了一個有趣的小故事红且，就是為了引出算法復(fù)雜度。
算法復(fù)雜度非常重要涤姊，要講的內(nèi)容也很多暇番，所以我們分為上下兩課。
當(dāng)程序員需要解決計算機(jī)科學(xué)相關(guān)的問題時思喊，他們（通常）會編寫一個程序壁酬。這個程序包含一個實現(xiàn)，也就是說需要把算法用一種編程語言來實現(xiàn)恨课。
我們知道舆乔，算法只是對解決問題的步驟的一種精確描述，它并不依賴于程序員所用的編程語言或工作環(huán)境剂公。
我們在 數(shù)據(jù)結(jié)構(gòu)和算法 | 第一部分第一課：什么是數(shù)據(jù)結(jié)構(gòu)和算法 里介紹了一個“煮方便面”的食譜希俩，這份食譜雖然簡單，但可以說是一個算法纲辽。
我們是用中文來描述這份食譜的颜武，如果我現(xiàn)在把這份食譜翻譯成一門外語（比如 英語），但食譜的內(nèi)容還是不變拖吼，只不過換了一種語言來說明罷了鳞上。換個英國人來照著這份英文食譜煮方便面，跟我做出來的會是一樣的绿贞。
那么因块，當(dāng)程序員需要把算法用一種編程語言來實現(xiàn)時，需要做什么呢籍铁？
像農(nóng)夫 Oscar 一樣涡上，他必須首先驗證他的算法是正確的趾断，也就是說它產(chǎn)生了預(yù)期的結(jié)果，解決了所涉及的問題吩愧。這非常重要（如果算法不正確芋酌，那我們根本沒有選擇和優(yōu)化它的必要），有時驗證算法正確性是非常難的一步雁佳。
算法正確性脐帝，英語是 Algorithm Correctness（algorithm 表示“算法”，correctness 表示“正確性”）糖权。要證明算法的正確性堵腹，有許多方法，我們本課程就不詳述了星澳，因為這不是我們的重點疚顷。大家有興趣可以去網(wǎng)上搜索一下。
當(dāng)然禁偎，算法正確了腿堤，并不能保證實現(xiàn)這個算法的程序就沒有錯誤（bug）。
一旦有了一個正確的算法如暖，我們用編程語言去實現(xiàn)它（通過編寫一個執(zhí)行它的程序）笆檀。但我們可能會寫出有很多小錯誤的程序，這些小錯誤也許和所使用的編程語言有關(guān)盒至，可能在編寫程序的過程中被引入酗洒。因為算法中一般不會描述如何避免犯錯，例如如何管理程序的內(nèi)存妄迁，如何檢查段錯誤（Segmentation Fault）寝蹈，等等，但這些都是程序員實現(xiàn)算法時需要考慮的問題登淘。
2. 算法的復(fù)雜度
一旦程序員確信他的算法是正確的，他將嘗試評估其效率封字，比如他會想知道“這個算法快不快”黔州。
有人可能會認(rèn)為，要知道算法快不快的最佳方式是實現(xiàn)該算法并在電腦上進(jìn)行測試阔籽。
有趣的是流妻，通常情況并非如此。例如笆制，如果兩個程序員實現(xiàn)了兩種不同的算法绅这，并在各自的電腦上測試程序運行的快慢。那么擁有更快速度的電腦的那個程序員可能會錯誤地認(rèn)為他的算法更快在辆，但其實并不一定证薇。
而且度苔，要實現(xiàn)一個算法并測試，有時候并不容易浑度。且不說有時候根據(jù)一個算法來寫出實現(xiàn)的代碼很難寇窑，如果要實現(xiàn)的算法涉及到一枚火箭的發(fā)射，難道每次用一枚真的火箭來發(fā)射一下去測試算法快不快嗎箩张？我們又不像鋼鐵俠那么有錢可以任性甩骏。
出于這些原因，計算機(jī)科學(xué)家們發(fā)明了一個非常方便而強(qiáng)大的概念先慷，也就是我們接下來要學(xué)習(xí)的：算法的復(fù)雜度饮笛。
“復(fù)雜度”（Complexity，表示“復(fù)雜”论熙，是一個名詞福青。它對應(yīng)的形容詞是 complex，表示“復(fù)雜的”）這個詞有點誤導(dǎo)人赴肚，因為我們這里不是強(qiáng)調(diào)“理解起來有困難”（很復(fù)雜素跺，很難），而是指效率（efficiency）誉券。
“復(fù)雜度”并不意味著“復(fù)雜的程度”指厌。有的算法理解起來很難（很復(fù)雜），它的復(fù)雜度卻可以非常低踊跟。
如果要用一句話來簡單說明算法復(fù)雜度踩验，那可以是：
“如果給實現(xiàn)了這個算法的程序一個大小為 N 的輸入，那么這個程序?qū)?zhí)行的操作的數(shù)目的數(shù)量級是 N 的一個怎么樣的函數(shù)（ f(N) ）呢商玫？”
f(N) 中的 f 是 function（函數(shù)）的意思箕憾，相信以前數(shù)學(xué)課的時候，大家都學(xué)過（比如我們以前很常見的 y = f(x) ）拳昌。f(N) 表示“N 的函數(shù)”袭异。
上面那句話基于以下事實：解決問題的程序取決于問題的起始條件。如果起始條件改變炬藤，程序執(zhí)行的時間也會變長或變短御铃。
復(fù)雜度可以量化（通過數(shù)學(xué)公式）起始條件與算法執(zhí)行的時間之間的關(guān)系。
上面這幾句話乍看有點難以理解沈矿。什么是操作上真？什么是操作的數(shù)目，什么是操作的數(shù)目的數(shù)量級羹膳？
不用擔(dān)心睡互，我們慢慢講解：
復(fù)雜度的學(xué)習(xí)中會涉及一些數(shù)學(xué)的概念。所以嘛，學(xué)好數(shù)學(xué)對編程還是很有幫助的就珠，英語同樣很重要寇壳。如果你英語和數(shù)學(xué)比較好，學(xué)起編程來會輕松很多嗓违【叛玻可以參看我以前的一篇文章：對于程序員, 為什么英語比數(shù)學(xué)更重要? 如何學(xué)習(xí) 。
數(shù)量級是指數(shù)量的尺度或大小的級別蹂季，每個級別之間保持固定的比例冕广。通常采用的比例有 10，2偿洁，1000撒汉，1024， e（歐拉數(shù)涕滋，大約等于 2.71828182846 的超越數(shù)睬辐，即自然對數(shù)的底）。
-- 摘自 百度百科
為了“計算操作的數(shù)目”宾肺，我們必須首先定義什么是操作溯饵。操作其實不難理解，比如第一部分第一課中锨用，我們講了一個“煮方便面”的算法丰刊，其中的步驟是這樣的：
- 在鍋子里倒入適量水
- 在爐子上點起火來（如果是電磁爐就不用火）
- 把鍋子放在爐子上
- 等待水開，轉(zhuǎn)中火
- 把方便面餅放入鍋中
- 煮半分鐘
- 放入所有調(diào)料包
- 煮 1 分鐘
- 出鍋
上面這些步驟中的每一步你都可以看成一個操作（operation增拥，“操作”的意思啄巧，這個英語單詞也有“運算”的意思）。
但是要計算操作的數(shù)目的時候掌栅，我們該挑選哪些操作呢? 即使是絕頂聰明的科學(xué)家可能也無法非常明確地回答秩仆。因為挑選哪些操作來做計算取決于所考慮的問題（甚至是算法）。
我們必須選擇算法經(jīng)常執(zhí)行的一些操作猾封，并且將其作為度量算法復(fù)雜度的基準(zhǔn)澄耍。
例如，要制作煎雞蛋晌缘，可以考慮三種基本操作：
- 打破雞蛋
- 鏟碎正在煎的雞蛋
- 煎熟雞蛋
因此逾苫，我們可以統(tǒng)計每份煎雞蛋的菜譜中的雞蛋數(shù)目，從而了解菜譜（算法）的復(fù)雜度（煎雞蛋是一個眾所周知的菜枚钓，我們可以預(yù)期所有煎雞蛋的菜譜都具有相同的復(fù)雜度：對于 N 個雞蛋，我們進(jìn)行 3N 個操作）瑟押。添加鹽搀捷、蔥、胡椒或其他佐料的操作非常快嫩舟，不需要考慮在菜譜（算法）復(fù)雜度之內(nèi)氢烘。
又例如，在上一課“小鴨子們?nèi)ヂ眯小钡墓适轮屑已幔b小鴨子的大箱子是 N 行 N 列播玖，那么如果農(nóng)夫 Oscar 采取第一種舊的算法，他須要在池塘和卡車之間進(jìn)行 N2（N 的平方）趟來回饭于；如果用第二種新的算法蜀踏，卻只須要 N 趟來回。
這是復(fù)雜度的一種很好的度量方式掰吕，因為農(nóng)夫 Oscar 在池塘和卡車之間來回這個過程是算法的所有操作里耗時最長的果覆。其他一些操作相對來說不那么耗時，比如 Oscar 從大箱子里挑出一只小鴨子殖熟，詢問小鴨子要去哪個池塘局待，等等。
因此菱属，我們可以說钳榨，此算法的總時間幾乎主要花在池塘和卡車之間來回這個操作上了，所以它可以作為度量此算法的效率的標(biāo)準(zhǔn)纽门。
如果復(fù)雜度的概念對你來說還是有點模糊薛耻，請不要擔(dān)心，之后的實踐課程應(yīng)該會讓你豁然開朗膜毁。
3. “漸近”度量
上面我們介紹了復(fù)雜度的基本概念昭卓，下面我們繼續(xù)講。
我們可以說：復(fù)雜度是算法的漸近行為的度量瘟滨。
漸近的英語是 Asymptotic候醒。那么，這個有點難以理解的詞“漸近行為”（或只是“漸進(jìn)”這個詞）是什么意思呢杂瘸？
這意味著“當(dāng)輸入變得非常大”（甚至“趨于無限”）時倒淫。這里的“輸入”是算法的起始條件的一種量化。
在“小鴨子們?nèi)ヂ眯小钡墓适轮邪苡瘢@意味著“當(dāng)大箱子里有很多行/列的小鴨子”時敌土，例如 N 是 250。在計算機(jī)科學(xué)中运翼，“很多”的含義卻略有不同：例如搜索引擎會說“有很多網(wǎng)頁”返干，1 萬億個網(wǎng)頁...
“當(dāng)輸入變得非常大”（甚至“趨于無限”）時會有兩種結(jié)果：
一方面，恒定的時間（是常量血淌，constant quantity）不予考慮矩欠。因為“恒定的時間”不依賴于輸入财剖。
例如，在農(nóng)夫 Oscar 開始將小鴨子們帶到每一個池塘去之前癌淮，他會先打開卡車的后車門躺坟。打開卡車后車門的時間被認(rèn)為是“恒定的”：不論他的大箱子里有 20 行 20 列小鴨子還是有 50 行 50 列小鴨子，開后車門都是花費相同的時間乳蓄。由于我們要考慮在大箱子的行/列的數(shù)目非常大的時候算法的效率咪橙，因此與 Oscar 在池塘和卡車之間來回的時間相比，打開卡車后車門的時間可以忽略不計虚倒。
另一方面美侦，“常數(shù)乘法因子”也不予考慮：復(fù)雜度的度量不區(qū)分執(zhí)行 N、2N 或 250N 個操作的算法裹刮。為什么呢音榜？我們考慮以下兩種取決于 N 的算法：
第一種算法：
做 N 次（操作A）
第二種算法：
做 N 次（操作B 然后 操作C）
在第一種算法中，我們做 N 次 操作A捧弃；在第二種算法中我們做 N 次 操作B赠叼，N 次 操作C。假設(shè)這兩種算法解決了同樣的問題（所以都是正確的）违霞，并且所有操作都被考慮進(jìn)復(fù)雜度的度量中：那么第一個算法做了 N 個操作嘴办，第二個算法做了 2N 個操作。
但我們可以說哪個算法更快嗎买鸽？當(dāng)然不行涧郊。因為這取決于 A、B眼五、C 這 3 個操作所花費的時間：也許 操作B 和 操作C 都比 操作A 快 4 倍妆艘，那么總體來看，操作數(shù)為 2N 的第二種算法比操作數(shù)為 N 的第一種算法反而更快看幼，因為 1/4 + 1/4 = 1/2（操作B 和 操作C 的耗時都是 操作A 的四分之一）批旺。
因此，不一定對算法的效率具有影響的常數(shù)乘法因子在復(fù)雜度的度量中不予考慮诵姜。
這也使我們能夠回答一開始的那個問題：如果兩個程序員有兩臺計算機(jī)汽煮，一臺比另一臺速度快 5 倍。5 這個常數(shù)乘法因子將被忽略棚唆，因此兩位程序員可以毫無問題地比較算法的復(fù)雜度暇赤。
可以看到，在算法的復(fù)雜度的度量中宵凌，我們忽略了很多東西鞋囊，這使得我們能有一個相當(dāng)簡單和普遍的概念。這種普遍性使復(fù)雜度成為一個有用的工具瞎惫，但它也有明顯的缺點：在某些非常特殊的情況下失暴，更復(fù)雜的算法居然可以用更少的時間來完成（例如坯门，常數(shù)因子在實際中也許能扮演非常關(guān)鍵的角色：假設(shè)農(nóng)夫 Oscar 的卡車后車門卡住了，他竟花了一整天的時間來打開后車門）逗扒。
然而，在絕大多數(shù)情況下欠橘，復(fù)雜度仍是算法性能的可靠指標(biāo)矩肩。特別是當(dāng)兩個復(fù)雜度之間的差距因為輸入的增大而變得越來越大時。
一種有 N 個比較耗時的操作的算法也許在 N 是 10 或 20 的時候比另一種有 N2（N 的平方）個不那么耗時的操作的算法運行時間更長肃续；但在 N 是 2萬 或 N 是 5 百萬的時候黍檩，復(fù)雜度更低的算法將肯定是更快的。
4. 第一部分第四課預(yù)告
今天的課有點難度始锚，不妨多讀幾遍刽酱。下一課我們繼續(xù)研究算法的復(fù)雜度。一起加油吧瞧捌！
下一課：數(shù)據(jù)結(jié)構(gòu)和算法 | 第一部分第四課：算法復(fù)雜度（下）
我是 謝恩銘棵里，公眾號「程序員聯(lián)盟」（微信號：coderhub）運營者，慕課網(wǎng)精英講師 Oscar 老師姐呐，終生學(xué)習(xí)者殿怜。
熱愛生活，喜歡游泳曙砂，略懂烹飪头谜。
人生格言：「向著標(biāo)桿直跑」
