真正統治世界的十大算法

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

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

　　什么是算法?

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

　　3. Dijkstra 算法

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

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

　　4. RSA算法

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

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

　　5. 安全哈希算法

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

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

　　6. 整數因式分解

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

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

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

　　7. 鏈接分析

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

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

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

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

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

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

　　8. 比例積分微分算法

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

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

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

　　9. 數據壓縮算法

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

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

　　10. 隨機數生成

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

　　(推薦閱讀：《當隨機不夠隨機：一個(gè)在線(xiàn)撲克游戲的教訓》)

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