十大改變世界的算法

來源 | 亂燉 python

Reddit 有篇帖子介紹了算法對我們現在生活的重要性，以及哪些算法對現代文明所做貢獻最大。這個表單並不完整，很多與我們密切相關的算法都沒有提到，如機器學習和矩陣乘法，歡迎你繼續補充。

如果對算法有所瞭解，讀這篇文章時你可能會問 “作者知道算法爲何物嗎？”，或是“Facebook 的‘信息流’(News Feed) 算是一種算法嗎？”，如果 “信息流” 是算法，那就可以把所有事物都歸結爲一種算法。才疏學淺，結合那篇帖子，接下來我試着解釋一下算法是什麼，又是哪些算法正在主導我們的世界。

「什麼是算法？」

「簡而言之，任何定義明確的計算步驟都可稱爲算法，接受一個或一組值爲輸入，輸出一個或一組值」。(來源：homas H. Cormen, Chales E. Leiserson 《算法導論第 3 版》)

可以這樣理解，算法是用來解決特定問題的一系列步驟（不僅計算機需要算法，我們在日常生活中也在使用算法）。算法必須具備如下 3 個重要特性：

其實，算法雖然廣泛應用在計算機領域，但卻完全源自數學。實際上，最早的數學算法可追溯到公元前 1600 年 - Babylonians 有關求因式分解和平方根的算法。

那麼又是哪 10 個計算機算法造就了我們今天的生活呢？請看下面的表單，排名不分先後：

01. 「歸併排序 (MERGE SORT)、快速排序(QUICK SORT) 和堆積排序(HEAP SORT)」

img

哪個排序算法效率最高？這要看情況。這也就是我把 3 種算法放在一起講的原因，可能你更常用其中一種，不過它們各有千秋。

歸併排序算法，是目前爲止最重要的算法之一，是分治法的一個典型應用，由數學家 John von Neumann 於 1945 年發明。

快速排序算法，結合了集合劃分算法和分治算法，不是很穩定，但在處理隨機列陣 (AM-based arrays) 時效率相當高。

堆積排序，採用優先佇列機制，減少排序時的搜索時間，同樣不是很穩定。

與早期的排序算法相比 (如冒泡算法)，這些算法將排序算法提上了一個大臺階。也多虧了這些算法，纔有今天的數據發掘，人工智能，鏈接分析，以及大部分網頁計算工具。

02. 「傅立葉變換和快速傅立葉變換」

img

這兩種算法簡單，但卻相當強大，整個數字世界都離不開它們，其功能是實現時間域函數與頻率域函數之間的相互轉化。能看到這篇文章，也是託這些算法的福。

因特網，WIFI，智能機，座機，電腦，路由器，衛星等幾乎所有與計算機相關的設備都或多或少與它們有關。不會這兩種算法，你根本不可能拿到電子，計算機或者通信工程學位。(USA)

03. 「迪傑斯特拉算法 (Dijkstra’s algorithm)」

img

可以這樣說，如果沒有這種算法，因特網肯定沒有現在的高效率。只要能以 “圖” 模型表示的問題，都能用這個算法找到 “圖” 中兩個節點間的最短距離。

雖然如今有很多更好的方法來解決最短路徑問題，但代克思託演算法的穩定性仍無法取代。

04. 「RSA 非對稱加密算法」

毫不誇張地說，如果沒有這個算法對密鑰學和網絡安全的貢獻，如今因特網的地位可能就不會如此之高。現在的網絡毫無安全感，但遇到錢相關的問題時我們必須要保證有足夠的安全感，如果你覺得網絡不安全，肯定不會傻乎乎地在網頁上輸入自己的銀行卡信息。

RSA 算法，密鑰學領域最牛叉的算法之一，由 RSA 公司的三位創始人提出，奠定了當今的密鑰研究領域。用這個算法解決的問題簡單又複雜：保證安全的情況下，如何在獨立平臺和用戶之間分享密鑰。

img

05. 「哈希算法 (Hash Algorithm)」

確切地說，這不是一種算法，而是一組加密哈希函數，由美國國家標準技術研究所首先提出。無論是你的應用商店，電子郵件和殺毒軟件，還是瀏覽器等等，都使用這種算法來保證你正常下載，以及是否被 “中間人攻擊”，或者 “網絡釣魚”。

img

06. 「整數質因子分解算法 (Integer factorization)」

這其實是一個數學算法，不過已經廣泛應用與計算機領域。如果沒有這個算法，加密信息也不會如此安全。通過一系列步驟將，它可以將一個合成數分解成不可再分的數因子。

很多加密協議都採用了這個算法，就比如剛提到的 RSA 算法。

img

img

在因特網時代，不同入口間關係的分析至關重要。從搜索引擎和社交網站，到市場分析工具，都在不遺餘力地尋找因特網的正真構造。

鏈接分析算法一直是這個領域最讓人費解的算法之一，實現方式不一，而且其本身的特性讓每個實現方式的算法發生異化，不過基本原理卻很相似。

鏈接分析算法的機制其實很簡單：你可以用矩陣表示一幅 “圖“，形成本徵值問題。本徵值問題可以幫助你分析這個“圖” 的結構，以及每個節點的權重。這個算法於 1976 年由 Gabriel Pinski 和 Francis Narin 提出。

誰會用這個算法呢？Google 的網頁排名，Facebook 向你發送信息流時 (所以信息流不是算法，而是算法的結果)，Google + 和 Facebook 的好友推薦功能，LinkedIn 的工作推薦，Youtube 的視頻推薦，等等。

普遍認爲 Google 是首先使用這類算法的機構，不過其實早在 1996 年 (Google 問世 2 年前) 李彥宏就創建的 “RankDex” 小型搜索引擎就使用了這個思路。而 Hyper Search 搜索算法建立者馬西莫 · 馬奇奧裏也曾使用過類似的算法。這兩個人都後來都成爲了 Google 歷史上的傳奇人物。

08. 「比例微積分算法 (Proportional Integral Derivative Algorithm)」

img

飛機，汽車，電視，手機，衛星，工廠和機器人等等事物中都有這個算法的身影。

簡單來講，這個算法主要是通過 “控制迴路反饋機制”，減小預設輸出信號與真實輸出信號間的誤差。只要需要信號處理，或電子系統來控制自動化機械，液壓和加熱系統，都需要用到這個算個法。

沒有它，就沒有現代文明。

09. 「數據壓縮算法」

數據壓縮算法有很多種，哪種最好？這要取決於應用方向，壓縮 mp3，JPEG 和 MPEG-2 文件都不一樣。

img

哪裏能見到它們？不僅僅是文件夾中的壓縮文件。你正在看的這個網頁就是使用數據壓縮算法將信息下載到你的電腦上。除文字外，遊戲，視頻，音樂，數據儲存，雲計算等等都是。它讓各種系統更輕鬆，效率更高。

010. 「隨機數生成算法」

到如今，計算機還沒有辦法生成 “正真的” 隨機數，但僞隨機數生成算法就足夠了。這些算法在許多領域都有應用，如網絡連接，加密技術，安全哈希算法，網絡遊戲，人工智能，以及問題分析中的條件初始化。

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/qizOGTzDhd7i1s2NZVLn6w

猜你喜歡