編程界稱霸全球的10大算法,你到底了解幾個呢?

thu數據派 發佈 2020-01-25T19:18:17+00:00

合併算法是迄今為止我們所擁有的最重要的算法之一,是分治法的一個典型應用,由數學家Johnvon Neumann於1945年發明。

來源:課程圖譜博客

本文約2300字,建議閱讀9分鐘

本文帶你了解編程界稱霸全球的十大算法。

算法究竟是什麼?

簡而言之,算法代表經過明確定義的計算過程,用於將輸入轉化為輸出。

可以這樣理解,算法是用來解決特定問題的一系列步驟(不僅計算機需要算法,我們在日常生活中也在使用算法)。就目前來看,具有以下三大特徵的算法才具備實際效果:

  • 有窮性:執行有限步驟後,算法必須終止;
  • 確切性:算法的每個步驟都必須確切定義;
  • 可行性:特定算法需可以在特定的時間內解決特定問題。

此外,需要強調的是,算法的應用不僅局限於計算機科學,同時它也作為一種數學實體。早在公元前1600年,巴比倫人就發現了用於求因式分解和平方根的算法。如果將算法視作數學實體,那麼稱霸世界的十大算法極可能為算術方法(如加、減、乘、除等)。

如果按照本文中算法的定義,稱霸世界的十種算法究竟有哪些呢?在這裡,我列出了一份小小的清單,排名不分先後。

合併排序、快速排序與堆排序

哪個排序算法效率最高?這要分情況討論。因此我將這3種算法放在一起來講,可能你更常用其中一種,但事實上三者都很重要。

合併算法是迄今為止我們所擁有的最重要的算法之一,是分治法的一個典型應用,由數學家John von Neumann於1945年發明。

快速排序算法,結合了集合劃分算法和分治算法,雖該算法並不是很穩定,但在對基於內存的數組進行排序時表現非常出色。

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

但這些算法相較於之前的冒泡排序等,有了很大的改進。也多虧了這些算法,才有今天的數據發掘,人工智慧,連結分析,以及大部分網頁計算工具。

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

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

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

迪傑斯特拉算法 (Dijkstra’s algorithm)

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

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

RSA非對稱加密算法

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

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

哈希安全算法(Secure Hash Algorithm)

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

整數質因子分解算法(Integer factorization)

這其實是一個數學算法,不過已經廣泛應用於計算機領域。如果沒有這個算法,密碼學技術的安全水平將受到嚴重破壞。該算法用於將複合數的質數因子分解到較小的非零因數。也被稱為FNP類問題,屬於NP類問題的拓展,且解決難度極高。

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

連結分析算法(Link Analysis)

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

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

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

誰會用這個算法呢?Google的網頁排名,Facebook向你發送信息流時(所以信息流不是算法,而是算法的結果),Google+和Facebook的好友推薦功能,LinkedIn的工作推薦,Youtube的視頻推薦,等等。雖然其各自擁有不同的目標與參數組合,但背後的數學原理卻是相通的。

最後,我想說一點,很多人普遍認為Google是首先使用這類算法的機構,不過其實早在1996年(Google 問世2年前)李彥宏就創建的「RankDex」小型搜尋引擎就使用了這個思路。而Hyper Search搜索算法建立者馬西莫·馬奇奧里也曾使用過類似的算法。這兩個人都後來都成為了Google歷史上的傳奇人物。

比例微積分算法

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

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

數據壓縮算法

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

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

隨機數生成算法

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

總結

總的來說,計算機的發展放到應用和數據飛速增長的大環境下,我們會發現:算法的重要性不是在日益減小,而是在日益加強。

本文連結地址:

http://blog.coursegraph.com/統計學公開課大盤點

編輯:於騰凱

—完—

關注清華-青島數據科學研究院官方微信公眾平台「 THU數據派 」及姊妹號「 數據派THU 」獲取更多講座福利及優質內容。

關鍵字: