影響我們世界的十大算法

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

現在，如果大家對於算法有些涉獵，那麼在讀過文章後的第一個想法很可能是——作者真的知道算法是什麼嗎?或者說 Facebook 新聞源是否屬於算法?因為如果 Facebook 新聞源也是一種算法，那麼我們幾乎可以把一切東西都歸結為算法。因此，我希望在本篇文章中解釋算法的真實定義，而後探討 10 種(或者更多)真正支配著整個世界的算法。

算法究竟是什麼?

直白地講，算法是指一切經過明確定義的計算過程，其將某個或者某組值作為輸入內容，併產生某個或者某組值作為輸出結果。因此，算法代表的是一系列計算步驟，用於將輸入轉換為輸出。——資源來源：Thomas H. Cormen 與 Chales E. Leiserson (2009 年)，《算法導論》第 3 版。

更簡單地總結，我們可以將算法視為一系列用於解決某個任務的步驟(是的，不僅僅是計算機會使用算法，人類同樣在使用算法)。就目前的標準來看，算法應當具有以下三大重要特徵才被視為擁有實際效果：

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

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

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

此外，需要強調的是算法的應用不僅侷限於計算科學，同時它也作為一種數學實體。事實上，早在公元前 1600 年就已經出現第一條記錄在案的數學算法——巴比倫人發現了最早的已知算法，用於分解平方根。因此，回到文章開頭我們討論的問題，我讀到的那篇文章將算法視為計算實體，但如果採取這樣一個更為寬泛的定義，那麼支配世界的十大算法很可能體現為算術方法(例如減法、乘法等)。

但是，如果採取我們在本文中做出的算法定義，那麼問題仍然存在：支配世界的十種算法究竟有哪些?在這裡，我列出一份小小的清單，排名不分先後。

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

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

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

快速排序是另一種用於解決排序問題的方法，其能夠實現就地分區，同樣屬於一類分而治之的算法。該算法的問題在於其在排序方面並不穩定，但在對基於內存的數組進行排序時表現出色。

最後是堆排序算法，其利用優先級隊列來減少數據中的搜索時間。該算法同樣屬於就地算法，且同樣不屬於穩定排序。

這些算法相較於我們之前使用過的其它方法(例如冒泡排序)有了很大的改進。事實上，正是由於這些算法的出現，我們才得以迎來數據挖掘、人工智能等網絡上常見的眾多現代計算工具。

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

整個數字世界都在使用這些簡單但非常強大的算法，這些算法能夠將信號從時域轉換為頻域，反之亦然。事實上，正是由於這些算法的存在，本篇文章才能被更多朋友所看到。

互聯網、Wi-Fi、智能手機、電話、計算機、路由器以及衛星等幾乎一切具有內置計算裝置的設備都會以這樣或者那樣的方式使用這些算法以保持運行。如果不研究這些重要的算法，大家也不可能拿下電子學、計算機或者通信科學學位。

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

實事求是地講，如果沒有這種算法，互聯網根本無法像今天這樣保持高效運作。這種圖搜索算法具有多種應用方式，能夠將需要解決的問題建模為圖，並在其中找到兩個節點間的最短路徑。

今天，雖然我們已經擁有更好的最短路徑問題解決方案，但迪傑斯特拉算法仍然在強調穩定性的眾多系統當中得到廣泛應用。

4. RSA 算法

如果沒有加密與網絡安全機制作為保障，互聯網的重要程度不可能達到如今的水平。大家可能會想“胡說，國家安全局局和眾多情報機構的監控早就毀掉了互聯網安全”或者“互聯網根本就沒有安全可言，傻子才會相信這種安全宣傳”; 但必須承認，大多數人仍然具有一定程度的安全信心，否則你根本就不會通過互聯網進行消費。畢竟如果真的否定現有網絡體系的安全性，誰會願意在 Web 服務中輸入自己的信用卡號碼?

在密碼學領域，有一種算法仍然是目前世界上最重要的算法之一，這就是 RSA 算法。該算法由 RSA 公司的創始人們開發而成，使得密碼學成果得以供世界上的每個人隨意使用，甚至最終塑造了當今密碼學技術的實現方式。RSA 算法希望解決的問題是如何在獨立平臺及最終用戶之間共享公鑰，從而實現加密(當然，我認為 RSA 算法並沒能徹底解決這個問題，從業者們還需要在這個方向上投入更多努力)。

5. 安全哈希算法

這實際上並不是真正的算法，而是由 NIST(美國國家標準技術研究所)所開發的一系列加密散列函數。然而，該算法家族對於世界秩序的維持起到了至關重要的作用。從應用程序商店、電子郵件、防病毒軟件再到常用的網絡瀏覽器，這一切都在使用這類算法(實際上，使用的是由這類算法生成的哈希值)，用以確定你所下載的是否正是你希望獲得的內容，或者你是否已經成為中間人攻擊或者網絡釣魚攻擊的受害者。

6. 整數分解

這是一種在計算領域被大量採用的數學算法。如果沒有這種算法，密碼學技術的安全水平將受到嚴重破壞。該算法用於將複合數的質數因子分解為較小的非零因數。這也被稱為 FNP 類問題，屬於 NP 類問題的擴展，且解決難度極高。

很多加密協議都以分解大型複合整數或相關問題的難度為基礎——RSA 算法就是其中的典型代表。正是由於對任意整數進行因子分解的難度極高，才使得基於 RSA 的公鑰加密機制擁有較高的安全性水平。

量子計算的誕生大大降低了此類問題的解決難度，並開闢出一個全新的科學研究領域——利用量子特性保障系統安全。

新手小白零基礎學習大數據技術，成都加米穀大數據培訓機構，大數據開發、 ，免費預約試聽課，提前報名享學費優惠！

7. 鏈接分析

在互聯網時代下，分析不同實體間的關係當然非常重要。從搜索引擎到社交網絡再到營銷分析工具，每一方都在努力發現隨著時間推移而不斷變化的互聯網結構。

鏈接分析可以說是普羅大眾眼中最神秘也最難以理解的算法之一。問題在於，我們可以通過多種不同方法實現鏈接分析，而且多種特徵的存在使得每種算法間都存在著一定差異(允許對算法申請專利)，但其底層基礎卻又高度相似。

鏈接分析背後的基本思路非常簡單，即允許使用者以矩陣的形式表示圖形，從而將其轉化為特徵值問題。這一特徵值可以為我們提供衡量圖形結構以及各節點相對重要性的好方法。該算法由 Gabriel Pinski 與 Francis Narin 於 1976 年發明得出。

那麼，誰在使用這一算法?谷歌公司需要進行網頁排名，Facebook 需要發佈新聞提要(因此，我們將 Facebook 的新聞源服務視為算法結果，而非算法本身)，Google+ 與 Facebook 的好友推薦，LinkedIn 的工作崗位與聯繫人推薦，Netflix 與 Hulu 的影視關聯、YouTube 的相關視頻等等皆屬於這一類。雖然其各自擁有不同的目標與參數組合，但背後的數學原理卻是相通的。

最後，我想強調一點，雖然很多人認為谷歌公司似乎是第一家使用這種算法的企業，但早在 1996 年(谷歌公司誕生的兩年之前)，由 Robin Li 開發的 RankDex 小型搜索引擎已經開始利用這一基本思路進行頁面排名。最終，HyperSearch 的創始人 Massimo Marchiori 也開始使用這種基於單頁間關係的頁面排名算法。(谷歌在其申請的專利當中提到了這兩位奠基者。)

8. 比例微積分算法

大家應該都體驗過飛機、汽車、衛星服務或者手機網絡吧?有些朋友還在工廠當中看到過機器人設備。如果是這樣，那麼你已經見識到了這一算法的威力。

該算法旨在利用控制迴路反饋機制以最大程度控制期望輸出信號與實際輸出信號間的誤差。其適用於一切存在信號處理需求的場景，包括以自動化方式通過電子技術控制的機械、液壓或者熱力系統。

也可以說，如果沒有這種算法，那麼我們的現代文明將無從談起。

9. 數據壓縮算法

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

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

10. 隨機數生成算法

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

最後，我想補充一點：這份清單隻代表一種觀點，而非真正全面的列表。因為在機器學習、矩陣乘法以及分類等領域還存在著諸多堪稱文明社會根基的重要算法，而我在本文中並沒有明確提及。