統(tǒng)治全球的10大算法
時間：2021-09-29 15:24:21
手機看文章
掃描二維碼
隨時隨地手機看文章
[導讀]什么是算法？簡而言之，任何定義明確的計算步驟都可稱為算法，接受一個或一組值為輸入，輸出一個或一組值。(來源：homasH.Cormen,ChalesE.Leiserson《算法導論第3版》)可以這樣理解，算法是用來解決特定問題的一系列步驟（不僅計算機需要算法，我們在日常生活中也在使用算法）。算法必須具備如下3個重要特性：有窮性，執(zhí)行有限步驟后，算法必須中止。確切性，算法的每個步驟都必須確切定義。可行性，特定算法須可以在特定的時間內(nèi)解決特定問題。其實，算法雖然廣泛應用在計算機領域，但卻完全源自數(shù)學。實際上，最早的數(shù)學算法可追溯到公元前1600年-Babylonians有關求因式分解和平方根的算法...
什么是算法？簡而言之，任何定義明確的計算步驟都可稱為算法，接受一個或一組值為輸入，輸出一個或一組值。(來源：homas H. Cormen, Chales E. Leiserson 《算法導論第3版》)
可以這樣理解，算法是用來解決特定問題的一系列步驟（不僅計算機需要算法，我們在日常生活中也在使用算法）。算法必須具備如下3個重要特性：
其實，算法雖然廣泛應用在計算機領域，但卻完全源自數(shù)學。實際上，最早的數(shù)學算法可追溯到公元前1600年-Babylonians有關求因式分解和平方根的算法。
那么又是哪10個計算機算法造就了我們今天的生活呢？請看下面的表單，排名不分先后：
01歸并排序(MERGE SORT)、快速排序(QUICK SORT)和堆積排序(HEAP SORT)
哪個排序算法效率最高？這要看情況。這也就是我把3種算法放在一起講的原因，可能你更常用其中一種，不過它們各有千秋。
歸并排序算法，是目前為止最重要的算法之一，是分治法的一個典型應用，由數(shù)學家John von Neumann于1945年發(fā)明。
快速排序算法，結合了集合劃分算法和分治算法，不是很穩(wěn)定，但在處理隨機列陣(AM-based arrays)時效率相當高。
堆積排序，采用優(yōu)先佇列機制，減少排序時的搜索時間，同樣不是很穩(wěn)定。
與早期的排序算法相比(如冒泡算法)，這些算法將排序算法提上了一個大臺階。也多虧了這些算法，才有今天的數(shù)據(jù)發(fā)掘、人工智能、鏈接分析以及大部分網(wǎng)頁計算工具。02傅立葉變換和快速傅立葉變換
這兩種算法簡單，但卻相當強大，整個數(shù)字世界都離不開它們，其功能是實現(xiàn)時間域函數(shù)與頻率域函數(shù)之間的相互轉(zhuǎn)化。能看到這篇文章，也是托這些算法的福。
因特網(wǎng)、WIFI、智能機、座機、電腦、路由器、衛(wèi)星等幾乎所有與計算機相關的設備都或多或少與它們有關。不會這兩種算法，你根本不可能拿到電子，計算機或者通信工程學位。(USA)
03迪杰斯特拉算法 (Dijkstra’s algorithm)
可以這樣說，如果沒有這種算法，因特網(wǎng)肯定沒有現(xiàn)在的高效率。只要能以“圖”模型表示的問題，都能用這個算法找到“圖”中兩個節(jié)點間的最短距離。
雖然如今有很多更好的方法來解決最短路徑問題，但代克思托演算法的穩(wěn)定性仍無法取代。04RSA非對稱加密算法
毫不夸張地說，如果沒有這個算法對密鑰學和網(wǎng)絡安全的貢獻，如今因特網(wǎng)的地位可能就不會如此之高。現(xiàn)在的網(wǎng)絡毫無安全感，但遇到錢相關的問題時我們必需要保證有足夠的安全感，如果你覺得網(wǎng)絡不安全，肯定不會傻乎乎地在網(wǎng)頁上輸入自己的銀行卡信息。
RSA算法，密鑰學領域最牛叉的算法之一，由RSA公司的三位創(chuàng)始人提出，奠定了當今的密鑰研究領域。用這個算法解決的問題簡單又復雜：保證安全的情況下，如何在獨立平臺和用戶之間分享密鑰。05哈希安全算法(Secure Hash Algorithm)
確切地說，這不是一種算法，而是一組加密哈希函數(shù)，由美國國家標準技術研究所首先提出。無論是你的應用商店，電子郵件和殺毒軟件，還是瀏覽器等等，都使用這種算法來保證你正常下載，以及是否被“中間人攻擊”，或者“網(wǎng)絡釣魚”。06整數(shù)質(zhì)因子分解算法(Integer factorization)
這其實是一個數(shù)學算法，不過已經(jīng)廣泛應用與計算機領域。如果沒有這個算法，加密信息也不會如此安全。通過一系列步驟將，它可以將一個合成數(shù)分解成不可再分的數(shù)因子。
很多加密協(xié)議都采用了這個算法，就比如剛提到的RSA算法。07鏈接分析算法(Link Analysis)
在因特網(wǎng)時代，不同入口間關系的分析至關重要。從搜索引擎和社交網(wǎng)站，到市場分析工具，都在不遺余力地尋找因特網(wǎng)的正真構造。
鏈接分析算法一直是這個領域最讓人費解的算法之一，實現(xiàn)方式不一，而且其本身的特性讓每個實現(xiàn)方式的算法發(fā)生異化，不過基本原理卻很相似。
鏈接分析算法的機制其實很簡單：你可以用矩陣表示一幅“圖“，形成本征值問題。本征值問題可以幫助你分析這個“圖”的結構，以及每個節(jié)點的權重。這個算法于1976年由Gabriel Pinski和Francis Narin提出。
誰會用這個算法呢？Google的網(wǎng)頁排名，F(xiàn)acebook向你發(fā)送信息流時(所以信息流不是算法，而是算法的結果)，Google 和Facebook的好友推薦功能，LinkedIn的工作推薦，Youtube的視頻推薦，等等。
普遍認為Google是首先使用這類算法的機構，不過其實早在1996年(Google 問世2年前)李彥宏就創(chuàng)建的“RankDex”小型搜索引擎就使用了這個思路。而Hyper Search搜索算法建立者馬西莫·馬奇奧里也曾使用過類似的算法。這兩個人都后來都成為了Google歷史上的傳奇人物。08比例微積分算法(Proportional Integral Derivative Algorithm)
飛機，汽車，電視，手機，衛(wèi)星，工廠和機器人等等事物中都有這個算法的身影。
簡單來講，這個算法主要是通過“控制回路反饋機制”，減小預設輸出信號與真實輸出信號間的誤差。只要需要信號處理，或電子系統(tǒng)來控制自動化機械，液壓和加熱系統(tǒng)，都需要用到這個算個法。
沒有它，就沒有現(xiàn)代文明。09數(shù)據(jù)壓縮算法
數(shù)據(jù)壓縮算法有很多種，哪種最好？這要取決于應用方向，壓縮mp3，JPEG和MPEG-2文件都不一樣。
哪里能見到它們？不僅僅是文件夾中的壓縮文件。你正在看的這個網(wǎng)頁就是使用數(shù)據(jù)壓縮算法將信息下載到你的電腦上。除文字外，游戲，視頻，音樂，數(shù)據(jù)儲存，云計算等等都是。它讓各種系統(tǒng)更輕松，效率更高。
10隨機數(shù)生成算法
到如今，計算機還沒有辦法生成“正真的”隨機數(shù)，但偽隨機數(shù)生成算法就足夠了。這些算法在許多領域都有應用，如網(wǎng)絡連接，加密技術，安全哈希算法，網(wǎng)絡游戲，人工智能，以及問題分析中的條件初始化。
END
來源：網(wǎng)絡版權歸原作者所有，如有侵權，請聯(lián)系刪除。
▍
可以這樣理解，算法是用來解決特定問題的一系列步驟（不僅計算機需要算法，我們在日常生活中也在使用算法）。算法必須具備如下3個重要特性：
- 有窮性，執(zhí)行有限步驟后，算法必須中止。
- 確切性，算法的每個步驟都必須確切定義。
- 可行性，特定算法須可以在特定的時間內(nèi)解決特定問題。
其實，算法雖然廣泛應用在計算機領域，但卻完全源自數(shù)學。實際上，最早的數(shù)學算法可追溯到公元前1600年-Babylonians有關求因式分解和平方根的算法。
那么又是哪10個計算機算法造就了我們今天的生活呢？請看下面的表單，排名不分先后：
01歸并排序(MERGE SORT)、快速排序(QUICK SORT)和堆積排序(HEAP SORT)
哪個排序算法效率最高？這要看情況。這也就是我把3種算法放在一起講的原因，可能你更常用其中一種，不過它們各有千秋。
歸并排序算法，是目前為止最重要的算法之一，是分治法的一個典型應用，由數(shù)學家John von Neumann于1945年發(fā)明。
快速排序算法，結合了集合劃分算法和分治算法，不是很穩(wěn)定，但在處理隨機列陣(AM-based arrays)時效率相當高。
堆積排序，采用優(yōu)先佇列機制，減少排序時的搜索時間，同樣不是很穩(wěn)定。
與早期的排序算法相比(如冒泡算法)，這些算法將排序算法提上了一個大臺階。也多虧了這些算法，才有今天的數(shù)據(jù)發(fā)掘、人工智能、鏈接分析以及大部分網(wǎng)頁計算工具。02傅立葉變換和快速傅立葉變換
這兩種算法簡單，但卻相當強大，整個數(shù)字世界都離不開它們，其功能是實現(xiàn)時間域函數(shù)與頻率域函數(shù)之間的相互轉(zhuǎn)化。能看到這篇文章，也是托這些算法的福。
因特網(wǎng)、WIFI、智能機、座機、電腦、路由器、衛(wèi)星等幾乎所有與計算機相關的設備都或多或少與它們有關。不會這兩種算法，你根本不可能拿到電子，計算機或者通信工程學位。(USA)
03迪杰斯特拉算法 (Dijkstra’s algorithm)
可以這樣說，如果沒有這種算法，因特網(wǎng)肯定沒有現(xiàn)在的高效率。只要能以“圖”模型表示的問題，都能用這個算法找到“圖”中兩個節(jié)點間的最短距離。
雖然如今有很多更好的方法來解決最短路徑問題，但代克思托演算法的穩(wěn)定性仍無法取代。04RSA非對稱加密算法
毫不夸張地說，如果沒有這個算法對密鑰學和網(wǎng)絡安全的貢獻，如今因特網(wǎng)的地位可能就不會如此之高。現(xiàn)在的網(wǎng)絡毫無安全感，但遇到錢相關的問題時我們必需要保證有足夠的安全感，如果你覺得網(wǎng)絡不安全，肯定不會傻乎乎地在網(wǎng)頁上輸入自己的銀行卡信息。
RSA算法，密鑰學領域最牛叉的算法之一，由RSA公司的三位創(chuàng)始人提出，奠定了當今的密鑰研究領域。用這個算法解決的問題簡單又復雜：保證安全的情況下，如何在獨立平臺和用戶之間分享密鑰。05哈希安全算法(Secure Hash Algorithm)
確切地說，這不是一種算法，而是一組加密哈希函數(shù)，由美國國家標準技術研究所首先提出。無論是你的應用商店，電子郵件和殺毒軟件，還是瀏覽器等等，都使用這種算法來保證你正常下載，以及是否被“中間人攻擊”，或者“網(wǎng)絡釣魚”。06整數(shù)質(zhì)因子分解算法(Integer factorization)
這其實是一個數(shù)學算法，不過已經(jīng)廣泛應用與計算機領域。如果沒有這個算法，加密信息也不會如此安全。通過一系列步驟將，它可以將一個合成數(shù)分解成不可再分的數(shù)因子。
很多加密協(xié)議都采用了這個算法，就比如剛提到的RSA算法。07鏈接分析算法(Link Analysis)
在因特網(wǎng)時代，不同入口間關系的分析至關重要。從搜索引擎和社交網(wǎng)站，到市場分析工具，都在不遺余力地尋找因特網(wǎng)的正真構造。
鏈接分析算法一直是這個領域最讓人費解的算法之一，實現(xiàn)方式不一，而且其本身的特性讓每個實現(xiàn)方式的算法發(fā)生異化，不過基本原理卻很相似。
鏈接分析算法的機制其實很簡單：你可以用矩陣表示一幅“圖“，形成本征值問題。本征值問題可以幫助你分析這個“圖”的結構，以及每個節(jié)點的權重。這個算法于1976年由Gabriel Pinski和Francis Narin提出。
誰會用這個算法呢？Google的網(wǎng)頁排名，F(xiàn)acebook向你發(fā)送信息流時(所以信息流不是算法，而是算法的結果)，Google 和Facebook的好友推薦功能，LinkedIn的工作推薦，Youtube的視頻推薦，等等。
普遍認為Google是首先使用這類算法的機構，不過其實早在1996年(Google 問世2年前)李彥宏就創(chuàng)建的“RankDex”小型搜索引擎就使用了這個思路。而Hyper Search搜索算法建立者馬西莫·馬奇奧里也曾使用過類似的算法。這兩個人都后來都成為了Google歷史上的傳奇人物。08比例微積分算法(Proportional Integral Derivative Algorithm)
飛機，汽車，電視，手機，衛(wèi)星，工廠和機器人等等事物中都有這個算法的身影。
簡單來講，這個算法主要是通過“控制回路反饋機制”，減小預設輸出信號與真實輸出信號間的誤差。只要需要信號處理，或電子系統(tǒng)來控制自動化機械，液壓和加熱系統(tǒng)，都需要用到這個算個法。
沒有它，就沒有現(xiàn)代文明。09數(shù)據(jù)壓縮算法
數(shù)據(jù)壓縮算法有很多種，哪種最好？這要取決于應用方向，壓縮mp3，JPEG和MPEG-2文件都不一樣。
哪里能見到它們？不僅僅是文件夾中的壓縮文件。你正在看的這個網(wǎng)頁就是使用數(shù)據(jù)壓縮算法將信息下載到你的電腦上。除文字外，游戲，視頻，音樂，數(shù)據(jù)儲存，云計算等等都是。它讓各種系統(tǒng)更輕松，效率更高。
10隨機數(shù)生成算法
到如今，計算機還沒有辦法生成“正真的”隨機數(shù)，但偽隨機數(shù)生成算法就足夠了。這些算法在許多領域都有應用，如網(wǎng)絡連接，加密技術，安全哈希算法，網(wǎng)絡游戲，人工智能，以及問題分析中的條件初始化。
END
來源：網(wǎng)絡版權歸原作者所有，如有侵權，請聯(lián)系刪除。
▍
下載文檔
