支配世界的十大算法是什么？

事實上，早在公元前 1600 年就已經(jīng)出現(xiàn)第一條記錄在案的數(shù)學(xué)算法——巴比倫人發(fā)現(xiàn)了最早的已知算法，用于分解平方根。因此，回到文章開頭我們討論的問題，我讀到的那篇文章將算法視為計算實體，但如果采取這樣一個更為寬泛的定義，那么支配世界的十大算法很可能體現(xiàn)為算術(shù)方法（例如減法、乘法等）。

算法究竟是什么？

直白地講，算法是指一切經(jīng)過明確定義的計算過程，其將某個或者某組值作為輸入內(nèi)容，并產(chǎn)生某個或者某組值作為輸出結(jié)果。因此，算法代表的是一系列計算步驟，用于將輸入轉(zhuǎn)換為輸出。

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

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

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

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

此外，需要強(qiáng)調(diào)的是算法的應(yīng)用不僅局限于計算科學(xué)，同時它也作為一種數(shù)學(xué)實體。但是，如果采取我們在本文中做出的算法定義，那么問題仍然存在：支配世界的十種算法究竟有哪些？在這里，我列出一份小小的清單，排名不分先后。

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

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

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

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

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

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

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

3. 迪杰斯特拉算法（又譯戴克斯特拉算法）

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

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

4. RSA 算法

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

在密碼學(xué)領(lǐng)域，有一種算法仍然是目前世界上最重要的算法之一，這就是 RSA 算法。該算法由 RSA 公司的創(chuàng)始人們開發(fā)而成，使得密碼學(xué)成果得以供世界上的每個人隨意使用，甚至最終塑造了當(dāng)今密碼學(xué)技術(shù)的實現(xiàn)方式。RSA 算法希望解決的問題是如何在獨(dú)立平臺及最終用戶之間共享公鑰，從而實現(xiàn)加密。

5. 安全哈希算法

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

6. 整數(shù)分解

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

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

7. 鏈接分析

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

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

8. 比例微積分算法

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

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

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

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

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

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