前幾天，我在 Reddit 上面閑逛的時(shí)候，發(fā)現(xiàn)了一篇有趣的文章，名為《影響我們世界的十大算法》。作者 George Dvorsky 希望通過(guò)此文解釋算法在當(dāng)今世界上的重要意義，以及哪些算法為我們的文明做出突出貢獻(xiàn)。

現(xiàn)在，如果大家對(duì)于算法有些涉獵，那么在讀過(guò)文章后的第一個(gè)想法很可能是——作者真的知道算法是什么嗎?或者說(shuō) Facebook 新聞源是否屬于算法?因?yàn)槿绻?Facebook 新聞源也是一種算法，那么我們幾乎可以把一切東西都?xì)w結(jié)為算法。因此，我希望在本篇文章中解釋算法的真實(shí)定義，而后探討 10 種(或者更多)真正支配著整個(gè)世界的算法。

算法究竟是什么?

直白地講，算法是指一切經(jīng)過(guò)明確定義的計(jì)算過(guò)程，其將某個(gè)或者某組值作為輸入內(nèi)容，并產(chǎn)生某個(gè)或者某組值作為輸出結(jié)果。因此，算法代表的是一系列計(jì)算步驟，用于將輸入轉(zhuǎn)換為輸出。——資源來(lái)源：Thomas H. Cormen 與 Chales E. Leiserson (2009 年)，《算法導(dǎo)論》第 3 版。

更簡(jiǎn)單地總結(jié)，我們可以將算法視為一系列用于解決某個(gè)任務(wù)的步驟(是的，不僅僅是計(jì)算機(jī)會(huì)使用算法，人類同樣在使用算法)。就目前的標(biāo)準(zhǔn)來(lái)看，算法應(yīng)當(dāng)具有以下三大重要特征才被視為擁有實(shí)際效果：

應(yīng)該是有限的: 算法應(yīng)該在有限的時(shí)間內(nèi)用有限的步驟解決掉其旨在解決的問(wèn)題，也就是說(shuō)算法必須在有限的時(shí)間內(nèi)可以完成，要不然就沒(méi)有現(xiàn)實(shí)意義。

應(yīng)該具有明確的指令: 算法中的每個(gè)步驟必須經(jīng)過(guò)精確定義 ; 同時(shí)應(yīng)針對(duì)每種情況做出明確說(shuō)明。

應(yīng)該切實(shí)有效: 算法應(yīng)當(dāng)能夠解決其旨在解決的問(wèn)題。此外，算法應(yīng)該被證明可以單純利用紙筆工具實(shí)現(xiàn)收斂。

此外，需要強(qiáng)調(diào)的是算法的應(yīng)用不僅局限于計(jì)算科學(xué)，同時(shí)它也作為一種數(shù)學(xué)實(shí)體。事實(shí)上，早在公元前 1600 年就已經(jīng)出現(xiàn)第一條記錄在案的數(shù)學(xué)算法——巴比倫人發(fā)現(xiàn)了最早的已知算法，用于分解平方根。因此，回到文章開(kāi)頭我們討論的問(wèn)題，我讀到的那篇文章將算法視為計(jì)算實(shí)體，但如果采取這樣一個(gè)更為寬泛的定義，那么支配世界的十大算法很可能體現(xiàn)為算術(shù)方法(例如減法、乘法等)。

但是，如果采取我們?cè)诒疚闹凶龀龅乃惴ǘ�義，那么問(wèn)題仍然存在：支配世界的十種算法究竟有哪些?在這里，我列出一份小小的清單，排名不分先后。

1. 合并排序，快速排序與堆排序

 

 

對(duì)元素進(jìn)行排序的最佳算法是什么?具體答案取決于你的實(shí)際需要，因此我把這三種比較常用的排序算法列為同一類 ; 也許你更偏愛(ài)其中一種，但事實(shí)上三者都非常重要。

其中合并排序算法是迄今為止我們所擁有的最為重要的算法之一。這是一種基于比較的排序算法，以分治的方法解決原本時(shí)間復(fù)雜度為 O(n^2) 的問(wèn)題。該算法由數(shù)學(xué)家 John von Neumann 于 1945 年發(fā)明得出。

快速排序是另一種用于解決排序問(wèn)題的方法，其能夠?qū)崿F(xiàn)就地分區(qū)，同樣屬于一類分而治之的算法。該算法的問(wèn)題在于其在排序方面并不穩(wěn)定，但在對(duì)基于內(nèi)存的數(shù)組進(jìn)行排序時(shí)表現(xiàn)出色。

最后是堆排序算法，其利用優(yōu)先級(jí)隊(duì)列來(lái)減少數(shù)據(jù)中的搜索時(shí)間。該算法同樣屬于就地算法，且同樣不屬于穩(wěn)定排序。

這些算法相較于我們之前使用過(guò)的其它方法(例如冒泡排序)有了很大的改進(jìn)。事實(shí)上，正是由于這些算法的出現(xiàn)，我們才得以迎來(lái)數(shù)據(jù)挖掘、人工智能等網(wǎng)絡(luò)上常見(jiàn)的眾多現(xiàn)代計(jì)算工具。

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

 

 

整個(gè)數(shù)字世界都在使用這些簡(jiǎn)單但非常強(qiáng)大的算法，這些算法能夠?qū)⑿盘?hào)從時(shí)域轉(zhuǎn)換為頻域，反之亦然。事實(shí)上，正是由于這些算法的存在，本篇文章才能被更多朋友所看到。

互聯(lián)網(wǎng)、Wi-Fi、智能手機(jī)、電話、計(jì)算機(jī)、路由器以及衛(wèi)星等幾乎一切具有內(nèi)置計(jì)算裝置的設(shè)備都會(huì)以這樣或者那樣的方式使用這些算法以保持運(yùn)行。如果不研究這些重要的算法，大家也不可能拿下電子學(xué)、計(jì)算機(jī)或者通信科學(xué)學(xué)位。

3. 迪杰斯特拉算法(又譯戴克斯特拉算法)

 

 

實(shí)事求是地講，如果沒(méi)有這種算法，互聯(lián)網(wǎng)根本無(wú)法像今天這樣保持高效運(yùn)作。這種圖搜索算法具有多種應(yīng)用方式，能夠?qū)⑿枰�解決的問(wèn)題建模為圖，并在其中找到兩個(gè)節(jié)點(diǎn)間的最短路徑。

今天，雖然我們已經(jīng)擁有更好的最短路徑問(wèn)題解決方案，但迪杰斯特拉算法仍然在強(qiáng)調(diào)穩(wěn)定性的眾多系統(tǒng)當(dāng)中得到廣泛應(yīng)用。

4. RSA 算法

如果沒(méi)有加密與網(wǎng)絡(luò)安全機(jī)制作為保障，互聯(lián)網(wǎng)的重要程度不可能達(dá)到如今的水平。大家可能會(huì)想“胡說(shuō)，國(guó)家安全局局和眾多情報(bào)機(jī)構(gòu)的監(jiān)控早就毀掉了互聯(lián)網(wǎng)安全”或者“互聯(lián)網(wǎng)根本就沒(méi)有安全可言，傻子才會(huì)相信這種安全宣傳”; 但必須承認(rèn)，大多數(shù)人仍然具有一定程度的安全信心，否則你根本就不會(huì)通過(guò)互聯(lián)網(wǎng)進(jìn)行消費(fèi)。畢竟如果真的否定現(xiàn)有網(wǎng)絡(luò)體系的安全性，誰(shuí)會(huì)愿意在 Web 服務(wù)中輸入自己的信用卡號(hào)碼?

在密碼學(xué)領(lǐng)域，有一種算法仍然是目前世界上最重要的算法之一，這就是 RSA 算法。該算法由 RSA 公司的創(chuàng)始人們開(kāi)發(fā)而成，使得密碼學(xué)成果得以供世界上的每個(gè)人隨意使用，甚至最終塑造了當(dāng)今密碼學(xué)技術(shù)的實(shí)現(xiàn)方式。RSA 算法希望解決的問(wèn)題是如何在獨(dú)立平臺(tái)及最終用戶之間共享公鑰，從而實(shí)現(xiàn)加密(當(dāng)然，我認(rèn)為 RSA 算法并沒(méi)能徹底解決這個(gè)問(wèn)題，從業(yè)者們還需要在這個(gè)方向上投入更多努力)。

5. 安全哈希算法

這實(shí)際上并不是真正的算法，而是由 NIST(美國(guó)國(guó)家標(biāo)準(zhǔn)技術(shù)研究所)所開(kāi)發(fā)的一系列加密散列函數(shù)。然而，該算法家族對(duì)于世界秩序的維持起到了至關(guān)重要的作用。從應(yīng)用程序商店、電子郵件、防病毒軟件再到常用的網(wǎng)絡(luò)瀏覽器，這一切都在使用這類算法(實(shí)際上，使用的是由這類算法生成的哈希值)，用以確定你所下載的是否正是你希望獲得的內(nèi)容，或者你是否已經(jīng)成為中間人攻擊或者網(wǎng)絡(luò)釣魚(yú)攻擊的受害者。

6. 整數(shù)分解

這是一種在計(jì)算領(lǐng)域被大量采用的數(shù)學(xué)算法。如果沒(méi)有這種算法，密碼學(xué)技術(shù)的安全水平將受到嚴(yán)重破壞。該算法用于將復(fù)合數(shù)的質(zhì)數(shù)因子分解為較小的非零因數(shù)。這也被稱為 FNP 類問(wèn)題，屬于 NP 類問(wèn)題的擴(kuò)展，且解決難度極高。

很多加密協(xié)議都以分解大型復(fù)合整數(shù)或相關(guān)問(wèn)題的難度為基礎(chǔ)——RSA 算法就是其中的典型代表。正是由于對(duì)任意整數(shù)進(jìn)行因子分解的難度極高，才使得基于 RSA 的公鑰加密機(jī)制擁有較高的安全性水平。

量子計(jì)算的誕生大大降低了此類問(wèn)題的解決難度，并開(kāi)辟出一個(gè)全新的科學(xué)研究領(lǐng)域——利用量子特性保障系統(tǒng)安全。

7. 鏈接分析

 

 

在互聯(lián)網(wǎng)時(shí)代下，分析不同實(shí)體間的關(guān)系當(dāng)然非常重要。從搜索引擎到社交網(wǎng)絡(luò)再到營(yíng)銷分析工具，每一方都在努力發(fā)現(xiàn)隨著時(shí)間推移而不斷變化的互聯(lián)網(wǎng)結(jié)構(gòu)。

鏈接分析可以說(shuō)是普羅大眾眼中最神秘也最難以理解的算法之一。問(wèn)題在于，我們可以通過(guò)多種不同方法實(shí)現(xiàn)鏈接分析，而且多種特征的存在使得每種算法間都存在著一定差異(允許對(duì)算法申請(qǐng)專利)，但其底層基礎(chǔ)卻又高度相似。

鏈接分析背后的基本思路非常簡(jiǎn)單，即允許使用者以矩陣的形式表示圖形，從而將其轉(zhuǎn)化為特征值問(wèn)題。這一特征值可以為我們提供衡量圖形結(jié)構(gòu)以及各節(jié)點(diǎn)相對(duì)重要性的好方法。該算法由 Gabriel Pinski 與 Francis Narin 于 1976 年發(fā)明得出。

那么，誰(shuí)在使用這一算法?谷歌公司需要進(jìn)行網(wǎng)頁(yè)排名，F(xiàn)acebook 需要發(fā)布新聞提要(因此，我們將 Facebook 的新聞源服務(wù)視為算法結(jié)果，而非算法本身)，Google+ 與 Facebook 的好友推薦，LinkedIn 的工作崗位與聯(lián)系人推薦，Netflix 與 Hulu 的影視關(guān)聯(lián)、YouTube 的相關(guān)視頻等等皆屬于這一類。雖然其各自擁有不同的目標(biāo)與參數(shù)組合，但背后的數(shù)學(xué)原理卻是相通的。

最后，我想強(qiáng)調(diào)一點(diǎn)，雖然很多人認(rèn)為谷歌公司似乎是第一家使用這種算法的企業(yè)，但早在 1996 年(谷歌公司誕生的兩年之前)，由 Robin Li 開(kāi)發(fā)的 RankDex 小型搜索引擎已經(jīng)開(kāi)始利用這一基本思路進(jìn)行頁(yè)面排名。最終，HyperSearch 的創(chuàng)始人 Massimo Marchiori 也開(kāi)始使用這種基于單頁(yè)間關(guān)系的頁(yè)面排名算法。(谷歌在其申請(qǐng)的專利當(dāng)中提到了這兩位奠基者。)

8. 比例微積分算法

 

 

大家應(yīng)該都體驗(yàn)過(guò)飛機(jī)、汽車、衛(wèi)星服務(wù)或者手機(jī)網(wǎng)絡(luò)吧?有些朋友還在工廠當(dāng)中看到過(guò)機(jī)器人設(shè)備。如果是這樣，那么你已經(jīng)見(jiàn)識(shí)到了這一算法的威力。

該算法旨在利用控制回路反饋機(jī)制以最大程度控制期望輸出信號(hào)與實(shí)際輸出信號(hào)間的誤差。其適用于一切存在信號(hào)處理需求的場(chǎng)景，包括以自動(dòng)化方式通過(guò)電子技術(shù)控制的機(jī)械、液壓或者熱力系統(tǒng)。

也可以說(shuō)，如果沒(méi)有這種算法，那么我們的現(xiàn)代文明將無(wú)從談起。

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

很難確定哪種壓縮算法的重要性最高，因?yàn)楦鶕?jù)實(shí)際應(yīng)用需求，大家使用的算法可能包括 zip、mp3 乃至 JPEG 以及 MPEG-2 等等。但相信大家都能清晰地感受到這些算法在各類結(jié)構(gòu)中的重要作用。

除了最直觀的文件壓縮之外，大家還能在哪里看到壓縮算法的蹤影?很明顯，網(wǎng)頁(yè)會(huì)利用數(shù)據(jù)壓縮技術(shù)控制你需要下載的文件體積，此外視頻游戲、視頻、音樂(lè)、數(shù)據(jù)存儲(chǔ)、云計(jì)算以及數(shù)據(jù)庫(kù)等也都是數(shù)據(jù)壓縮算法大顯身手的舞臺(tái)。可以說(shuō)，萬(wàn)事萬(wàn)物都離不開(kāi)數(shù)據(jù)壓縮，這類算法的存在使得系統(tǒng)能夠以成本更低且效率更高的方式為用戶服務(wù)。

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

 

 

今天，我們還沒(méi)有“真正的”隨機(jī)數(shù)生成器，但已經(jīng)擁有眾多完全可以滿足需求的偽隨機(jī)數(shù)生成器。這些算法廣泛存在于互連鏈接、加密、安全哈希算法、視頻游戲、人工智能、優(yōu)化、問(wèn)題條件初始化以及財(cái)務(wù)等領(lǐng)域。

最后，我想補(bǔ)充一點(diǎn)：這份清單只代表一種觀點(diǎn)，而非真正全面的列表。因?yàn)樵跈C(jī)器學(xué)習(xí)、矩陣乘法以及分類等領(lǐng)域還存在著諸多堪稱文明社會(huì)根基的重要算法，而我在本文中并沒(méi)有明確提及。

原文鏈接The real 10 algorithms that dominate our world

標(biāo)簽： 算法

版權(quán)申明：本站文章部分自網(wǎng)絡(luò)，如有侵權(quán)，請(qǐng)聯(lián)系：west999com@outlook.com
特別注意：本站所有轉(zhuǎn)載文章言論不代表本站觀點(diǎn)！
本站所提供的圖片等素材，版權(quán)歸原作者所有，如需使用，請(qǐng)與原作者聯(lián)系。