不久前的某一天，我在瀏覽Reddit發(fā)現(xiàn)了一篇有趣的文章《統(tǒng)治世界的十大算法》，作者George Dvorsky在那篇文章中試圖解釋算法之于當(dāng)今世界的重要性，以及哪些算法對(duì)人類文明最為重要。

　　此時(shí)此刻，如果你已經(jīng)學(xué)過(guò)算法的話，那么在你閱讀那篇文章時(shí)，你腦海中所浮現(xiàn)的第一件事也許是“作者是否明白算法是什么?”或是“Facebook的新聞提要是一種算法?”，因?yàn)槿绻鸉acebook的新聞提要也算是一種算法的話，那么最終你可以把幾乎所有的東西都?xì)w類為算法。因此，在本文中我會(huì)試著去解釋什么是算法，以及哪十個(gè)(也許更多)算法是真正統(tǒng)治世界的。

　　什么是算法?

　　直白地說(shuō)，算法就是任何明確定義的計(jì)算過(guò)程，它接收一些值或集合作為輸入，并產(chǎn)生一些值或集合作為輸出。這樣，算法就是將輸入轉(zhuǎn)換為輸出的一系列計(jì)算過(guò)程。來(lái)源：Thomas H. Cormen, Chales E. Leiserson (2009), 《算法導(dǎo)論第三版》。

　　簡(jiǎn)而言之，我們可以說(shuō)算法就是用來(lái)解決一個(gè)特定任務(wù)的一系列步驟(是的，不止計(jì)算機(jī)在使用算法，人類也同樣如此)。目前，一個(gè)有效的算法應(yīng)該含有三個(gè)重要特性：

　　1. 它必須是有限的：如果你設(shè)計(jì)的算法永無(wú)休止地嘗試解決問(wèn)題，那么它是無(wú)用的。

　　2. 它必須具備明確定義的指令：算法的每一步都必須準(zhǔn)確定義，在任何場(chǎng)景下指令都應(yīng)當(dāng)沒(méi)有歧義。

　　3. 它必須是有效的：一個(gè)算法被設(shè)計(jì)用以解決某個(gè)問(wèn)題，那么它就應(yīng)當(dāng)能解決這個(gè)問(wèn)題，并且僅僅使用紙和筆就能證明該算法是收斂的。

　　還有一個(gè)要點(diǎn)需要指出，算法不僅僅在計(jì)算機(jī)科學(xué)中使用，同時(shí)也存在于數(shù)學(xué)領(lǐng)域中。事實(shí)上，首個(gè)被記載的數(shù)學(xué)算法要追溯到公元前1600年，古巴比倫人開發(fā)了已知最早的算法，用作因式分解和計(jì)算平方根。這里，我們回答了前面所提到的那篇文章中的第一個(gè)問(wèn)題，它認(rèn)為算法是計(jì)算機(jī)范疇的實(shí)體，但如果你知曉算法這個(gè)詞的真正內(nèi)涵的話，真正統(tǒng)治世界的十大算法也能在數(shù)學(xué)書籍中找到(加法、減法、乘積等等)。

　　不過(guò)在這篇文章中，讓我們將算法的定義限定在計(jì)算機(jī)算法上，所以剩下的問(wèn)題是：哪十個(gè)算法統(tǒng)治了世界?在此我整理了一個(gè)小型列表，排名不分先后。

　　1. 歸并排序，快速排序和堆排序

　　哪個(gè)排序算法最好?這取決于你的需求，這也是為什么我要將這三個(gè)使用頻率較高的排序算法置于一處的原因。可能你比較偏愛(ài)其中一個(gè)，但它們都是同等重要的。

　　歸并排序算法是目前為止我們擁有的最重要的算法之一。它是一種基于比較的排序算法，使用分治法解決那些原本復(fù)雜度為O(N^2)的問(wèn)題。歸并排序是由數(shù)學(xué)家John von Neumann于1945年發(fā)明的。

　　快速排序是解決排序問(wèn)題的另一種途徑，它使用就地分解算法，同時(shí)它也是一種分治算法。這個(gè)算法的問(wèn)題在于它是不穩(wěn)定的排序算法，但它在基于內(nèi)存的數(shù)組排序上確實(shí)非常高效。

　　最后，堆排序算法使用一個(gè)優(yōu)先隊(duì)列降低數(shù)據(jù)的查找時(shí)間，它也是一種就地排序算法，同樣也是不穩(wěn)定的排序算法。

　　相較于曾經(jīng)使用的其他排序算法(如冒泡排序)，上述算法帶來(lái)了顯著的改進(jìn)。事實(shí)上，多虧了它們，今天我們才有了數(shù)據(jù)挖掘、人工智能、鏈接分析，以及世界上大部分的計(jì)算機(jī)工具，也包括網(wǎng)絡(luò)在內(nèi)。

　　(推薦閱讀：《視覺(jué)直觀感受 7 種常用的排序算法》)

　　2. 傅立葉變換與快速傅立葉變換

　　整個(gè)數(shù)字世界都在使用這些簡(jiǎn)單而又強(qiáng)大的算法，將信號(hào)從頻域轉(zhuǎn)換為時(shí)域，反之亦然。事實(shí)上，正是歸功于這些算法，你才能看到這篇文章。

　　互聯(lián)網(wǎng)、你的WIFI、智能手機(jī)、電話、計(jì)算機(jī)、路由器、衛(wèi)星，幾乎所有內(nèi)置計(jì)算機(jī)的東西都會(huì)以各種方式使用這些算法實(shí)現(xiàn)各自的功能。如果你沒(méi)有學(xué)習(xí)這些重要的算法，你將無(wú)法獲得電子、計(jì)算機(jī)或通信方面的學(xué)位。

　　編注：關(guān)于傅里葉變換，可以看看韓昊寫的這篇文章《通俗講解傅里葉變換【完整版】》。

　　3. Dijkstra 算法

　　毫無(wú)不夸張地說(shuō)，如果沒(méi)有這個(gè)算法，當(dāng)今互聯(lián)網(wǎng)將無(wú)法有效工作。這是一種圖搜索算法，它被廣泛應(yīng)用在能夠建模為圖的問(wèn)題中，用以找出兩個(gè)節(jié)點(diǎn)之間的最短路徑。

　　目前，即便我們已經(jīng)擁有了解決最短路徑問(wèn)題的更好方法，Dijkstra 算法依然在那些重視穩(wěn)定性的系統(tǒng)中得到應(yīng)用。

　　4. RSA算法

　　如果沒(méi)有信息加密和網(wǎng)絡(luò)安全，互聯(lián)網(wǎng)不會(huì)像現(xiàn)在那么重要。你可以認(rèn)為“安全問(wèn)題理所當(dāng)然應(yīng)該是美國(guó)國(guó)家安全局和其他情報(bào)機(jī)構(gòu)的事情”或“你認(rèn)為你身處在互聯(lián)網(wǎng)是安全的，這太天真了”。但是，人們需要在他們花錢時(shí)保有安全感，畢竟你不會(huì)在網(wǎng)絡(luò)服務(wù)器上輸入你的信用卡號(hào)，如果你知道它是不安全的話。

　　在信息加密領(lǐng)域，有一個(gè)算法始終是世界上最重要的算法之一，它就是RSA算法。這個(gè)算法是由RSA公司的創(chuàng)始人所建立的，它使信息加密惠及千家萬(wàn)戶，奠定了當(dāng)今信息加密的運(yùn)作基礎(chǔ)。RSA算法用來(lái)解決一個(gè)簡(jiǎn)單而又復(fù)雜的問(wèn)題：怎樣在不同平臺(tái)和終端用戶之間共享公鑰，繼而實(shí)現(xiàn)信息加密(我想說(shuō)明一下這個(gè)問(wèn)題還沒(méi)完全解決，我想我們需要基于這個(gè)方向做更多工作)。

　　5. 安全哈希算法

　　準(zhǔn)確地說(shuō)，它不能稱之為是算法，它是美國(guó)國(guó)家標(biāo)準(zhǔn)暨技術(shù)學(xué)會(huì)定義的加密散列函數(shù)族中的一員，但是這族算法對(duì)整個(gè)世界的運(yùn)作至關(guān)重要。從你的應(yīng)用商店，你的郵件，你的殺毒軟件，到你的瀏覽器等等，所有這些都在使用安全哈希算法，它能判斷你是否下載了你想要的東西，也能判斷你是否是中間人攻擊或網(wǎng)絡(luò)釣魚攻擊的受害者。

　　(推薦閱讀：《加鹽密碼哈希：如何正確使用》)

　　6. 整數(shù)因式分解

　　這是在計(jì)算機(jī)領(lǐng)域被大量使用的數(shù)學(xué)算法，沒(méi)有這個(gè)算法，信息加密會(huì)更不安全。該算法定義了一系列步驟，得到將一合數(shù)分解為更小因子的質(zhì)數(shù)分解式。這被認(rèn)為是一種FNP問(wèn)題，它是NP分類問(wèn)題的延伸，極其難以解決。

　　許多加密協(xié)議(如RSA算法)都基于這樣一個(gè)原理：對(duì)大的合數(shù)作因式分解是非常困難的。如果一個(gè)算法能夠快速地對(duì)任意整數(shù)進(jìn)行因式分解，RSA的公鑰加密體系就會(huì)失去其安全性。

　　量子計(jì)算的誕生使我們能夠更容易地解決這類問(wèn)題，同時(shí)它也打開了一個(gè)全新的領(lǐng)域，使得我們能夠利用量子世界中的特性來(lái)保證系統(tǒng)安全。

　　7. 鏈接分析

　　在互聯(lián)網(wǎng)時(shí)代，分析不同實(shí)體間的關(guān)系是相當(dāng)重要的。從搜索引擎，社交網(wǎng)絡(luò)，到營(yíng)銷分析工具，每個(gè)人都在不停尋找互聯(lián)網(wǎng)的真正結(jié)構(gòu)。

　　有證據(jù)顯示，鏈接分析是公眾心目中伴隨著最多謬見和誤解的算法之一。這里的問(wèn)題在于，有很多不同的方式可以進(jìn)行鏈接分析，也存在很多特性使這些算法看起來(lái)有細(xì)微的區(qū)別(這些區(qū)別允許該算法獨(dú)立申請(qǐng)專利)，但它們本質(zhì)上是類似的。

　　鏈接分析背后的理念非常簡(jiǎn)單，以矩陣形式描繪出一張圖，將問(wèn)題轉(zhuǎn)換為特征值問(wèn)題。特征值是一種很好的渠道，它有助于展現(xiàn)圖的結(jié)構(gòu)以及每個(gè)節(jié)點(diǎn)的相對(duì)重要性。該算法是由Gabriel Pinski和Francis Narin于1976年建立的。

　　誰(shuí)在使用這個(gè)算法?Google的Page Rank算法，F(xiàn)acebook向你展示的新聞提要(這就是為什么Facebook的新聞提要不是算法，只是使用算法的結(jié)果而已)，Google+和Facebook的好友推薦，LinkedIn的工作和聯(lián)系人推薦，Netflix和Hulu的電影，YouTuBe的視頻，等等。雖然每個(gè)都有不同的目標(biāo)和參數(shù)，但它們背后的數(shù)學(xué)理念是相同的。

　　最后，我想說(shuō)明一點(diǎn)，盡管看上去Google是第一家使用這類算法的公司，然而在1996年(Google之前兩年)，Robin Li(李彥宏)所建立的一個(gè)小型搜索引擎“RankDex”就已經(jīng)在它的網(wǎng)頁(yè)排名機(jī)制中使用了這項(xiàng)理念。后來(lái)，HyperSearch的創(chuàng)始人Massimo Marchiori基于各網(wǎng)頁(yè)之間的關(guān)系使用了另一種網(wǎng)頁(yè)排名算法。(Google在它的專利中提到了這兩位創(chuàng)始者)

　　(推薦閱讀：《張洋：淺析PageRank算法)

　　8. 比例積分微分算法

　　你是否曾經(jīng)用過(guò)飛機(jī)、汽車、衛(wèi)星服務(wù)或手機(jī)網(wǎng)絡(luò)?你是否曾經(jīng)在工廠工作或是看見過(guò)機(jī)器人?如果回答是肯定的，那么你應(yīng)該已經(jīng)見識(shí)過(guò)這個(gè)算法了。

　　大體上，這個(gè)算法使用一種控制回路反饋機(jī)制，將期望輸出信號(hào)和實(shí)際輸出信號(hào)之間的錯(cuò)誤最小化。無(wú)論何處，只要你需要進(jìn)行信號(hào)處理，或者你需要一套電子系統(tǒng)，用來(lái)自動(dòng)化控制機(jī)械、液壓或熱力系統(tǒng)，這個(gè)算法都會(huì)有用武之地。

　　可以這樣說(shuō)，如果沒(méi)有這個(gè)算法，現(xiàn)代文明將不復(fù)存在。

　　9. 數(shù)據(jù)壓縮算法

　　要判斷哪種數(shù)據(jù)壓縮算法最為重要是很困難的，因?yàn)樗Q于不同的應(yīng)用環(huán)境。它們可以應(yīng)用在zip和mp3上，也可以應(yīng)用在JPEG和MPEG-2上。但眾所周知，在所有結(jié)構(gòu)中這些算法都極其重要。

　　除了顯而易見的zip文件，在哪我們能夠找到這些算法?這張網(wǎng)頁(yè)就進(jìn)行了數(shù)據(jù)壓縮并被下載到你本地，同時(shí)我們還能在電子游戲、視頻、音樂(lè)、數(shù)據(jù)存儲(chǔ)、云計(jì)算、數(shù)據(jù)庫(kù)等等地方找到這些算法。可以說(shuō)，數(shù)據(jù)壓縮算法處處可見，它們使系統(tǒng)成本更低、效率更高。

　　10. 隨機(jī)數(shù)生成

　　現(xiàn)在我們還沒(méi)有一個(gè)“真正的”隨機(jī)數(shù)生成器，但我們已經(jīng)有了一些偽隨機(jī)數(shù)生成器，這夠用了。隨機(jī)數(shù)生成器的用途非常廣泛，從互聯(lián)聯(lián)絡(luò)、數(shù)據(jù)加密、安全哈希算法、電子游戲、人工智能、優(yōu)化分析，到問(wèn)題的初始條件、金融等等，都有它們的身影。

　　(推薦閱讀：《當(dāng)隨機(jī)不夠隨機(jī)：一個(gè)在線撲克游戲的教訓(xùn)》)

　　最后，我想強(qiáng)調(diào)一下，上面這個(gè)列表經(jīng)供參考，它并不完整。因?yàn)樵跈C(jī)器學(xué)習(xí)、矩陣乘法、分類化等領(lǐng)域也有一些算法，它們對(duì)我們的世界同樣重要，但在這里還沒(méi)有提到。