真正統(tǒng)治世界的十大算法

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

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

　　什么是算法?

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

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

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

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

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

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

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

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

　　哪個排序算法最好?這取決于你的需求，這也是為什么我要將這三個使用頻率較高的排序算法置于一處的原因?？赡苣惚容^偏愛其中一個，但它們都是同等重要的。

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

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

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

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

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

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

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

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

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

　　3. Dijkstra 算法

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

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

　　4. RSA算法

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

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

　　5. 安全哈希算法

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

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

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

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

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

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

　　7. 鏈接分析

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

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

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

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

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

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

　　8. 比例積分微分算法

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

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

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

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

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

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

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

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

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

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