真正支配整個世界的十種演算法

作者 | Marcos Otero

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

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

http://the%2010%20algorithms%20that%20dominate%20our%20world/

演算法究竟是什麼？

直白地講，演算法是指一切經過明確定義的計算過程，其將某個或者某組值作為輸入內容，併產生某個或者某組值作為輸出結果。因此，演算法代表的是一系列計算步驟，用於將輸入轉換為輸出。

資源來源：Thomas H. Cormen 與 Chales E. Leiserson (2009 年)，《演算法導論》第 3 版。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

《演算法面試通關 40 講》視頻課，碼上訂閱

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. 隨機數生成演算法

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

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

英文原文

https://medium.com/@_marcos_otero/the-real-10-algorithms-that-dominate-our-world-e95fa9f16c04

課程推薦

最後 2 天優惠｜推薦《演算法面試通關 40 講》視頻課，演算法與數據結構是每個程序員的基本功，演算法面試是每個程序員求職進大廠繞不開的話題。前 Facebook 工程師覃超為你講解常見演算法知識點理論，剖析高頻面試題目思路，傳授 LeetCode 高效解題四步法，讓你有效提升演算法面試通過率。現在訂閱，有以下福利：

福利一：限時優惠價￥99 元，原價￥129 元，10 月 20 日恢復原價

福利二：每邀請一位好友購買，你可獲得 24 元現金返現，多邀多得，上不封頂，隨時提現。（提現流程：極客時間 App - 我的 - 分享有賞）

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！