[算法] 當今世界最為經典的十大算法--投票進行時

當今世界最為經典的十大算法--投票進行時

----------------------------------------

第一部分、來自聖經的十大算法

第十名：Huffman coding（霍夫曼編碼）

    霍夫曼編碼(Huffman Coding)是一種編碼方式，是一種用于無損資料壓縮的熵編碼（權編碼）算法。1952年，David A. Huffman在麻省理工攻讀博士時所發明的，并發表于《一種建構極小多餘編碼的方法》（A Method for the Construction of Minimum-Redundancy Codes）一文。

第九名：Binary Search （二分查找）

第八名：Miller-Rabin 作的類似的試驗測試

    這個想法是利用素數的性質(如使用費馬大定理)的小機率尋找見證不數素數。如果沒有證據是足夠的随機檢驗後發現,這一數字為素數。

第七名：DFS BFS（深度、廣度優先搜尋） 它們是許多其他算法的基礎。

第六名：Gentry's Fully Homomorphic Encryption Scheme（紳士完全同态加密機制）算法。

    此算法很漂亮，它允許第三方執行任意加密資料運算得不到私鑰（不是很了解）。

第五名：Floyd-Warshall all-pairs 最短路徑算法

d[]: 二維數組. d[i,j]最小花費、或最短路徑的鄰邊。

for k from 1 to n:

  for i from 1 to n:

    for j from 1 to n:

      d[i,j] = min(d[i,j], d[i,k] + d[k,j])

第四名：Quicksort（快速排序）

    快速排序算法幾乎涵蓋了所有經典算法的所有榜單。它曾獲選二十世紀最偉大的十大算法（參考這：細數二十世紀最偉大的10大算法）。關于快速排序算法的具體介紹，請參考我寫的這篇文章：一之續、快速排序算法的深入分析，及十二、一之再續：快速排序算法之所有版本的c/c++實作。

第三名：BFPRT 算法

    1973 年，Blum、Floyd、Pratt、Rivest、Tarjan一起釋出了一篇名為 “Time bounds for selection” 的論文，給出了一種在數組中選出第k大元素平均複雜度為O（N）的算法，俗稱"中位數之中位數算法"。這個算法依靠一種精心設計的 pivot 選取方法，即選取中位數的中位數作為樞紐元，進而保證了在最壞情況下的也能做到線性時間的複雜度，打敗了平均O（N*logN）、最壞 O(n^2) 複雜度的快速排序算法。

    事實上，這個所謂的BFPRT，就是本blog中闡述過的快速選擇SELECT算法，詳情請參考下列博文：第三章、尋找最小的k個數、十四、快速選擇SELECT算法的深入分析與實作。在我的這兩篇文章中，給出了此快速選擇SELECT算法，借助選取數組中中位數的中位數作為樞紐元，能做到最壞情況下運作時間為O（N）的複雜度的證明。

    我在這裡簡單介紹下在數組中選出第k大元素的時間複雜度為O（N）的算法：

    類似快排中的分割算法：

每次分割後都能傳回樞紐點在數組中的位置s,然後比較s與k的大小

若大的話，則再次遞歸劃分array[s..n]，

小的話，就遞歸array[left...s-1] //s為中間樞紐點元素。

否則傳回array[s]，就是partition中傳回的值。 //就是要找到這個s。

找到符合要求的s值後，再周遊輸出比s小的那一邊的元素。

    各位還可參考在：算法導論上，第九章中，以期望線性時間做選擇，有尋找數組中第k小的元素的，平均時間複雜度為O（N）的證明。原程式随機選取數組中某一進制素作為樞紐元，最後可證得程式的期望運作時間為O(n)，且假定元素是不同的。

第二名：Knuth-Morris-Pratt字元串比對算法

    關于此算法的介紹，請參考此文：六、教你從頭到尾徹底了解KMP算法。KMP算法曾經落選于二十世紀最偉大的十大算法，但人們顯然不能接受，如此漂亮、高效的KMP算法竟然會落選。是以，此次最終投票産出生，KMP算法排到了第二名。

第一名：Union-find

    并查集是一種樹型的資料結構，用于處理一些不相交集合（Disjoint Sets）的合并及查詢問題。常常在使用中以森林來表示。集就是讓每個元素構成一個單元素的集合，并就是按一定順序将屬于同一組的元素所在的集合合并。并行查找，最終占據了此份榜單的第一名。

    補充：前三名的投票數，隻相差4票，8票。是以這個排名日後還會不斷有所變化。但不管最終結果怎樣，這前十名的算法已經基本敲定了。

    原投票網址：http://cstheory.stackexchange.com/questions/189/algorithms-from-the-book。

第二部分、當今世界最為經典的十大算法--投票進行時

    怎麼樣，上文那些投票産生出來的來自聖經的算法，你是否熟悉?或者，如果要您選出您心目中，當今世界最為經典的十大算法，您肯定也、絕對不一定認同上述十個所謂來自聖經的算法便是當今世界最為經典的十大算法，對吧?ok，那麼，現在，我給你一個投票權，你會把票投給哪一個算法列?好的，咱們也來一次投票吧，請把你的意見，決定權寫在本文下面的評論裡。

    我把已經産生的前十名的算法，再寫在下面，友善投票（投票截止日期：三年後的今天，即二零一四年三月七日）：

一、Huffman coding（霍夫曼編碼）。

二、Binary Search （二分查找）。

三、Miller-Rabin作的類似的試驗測試。

四、Depth First Search（深度優先搜尋）。

五、紳士完全同态加密機制

六、Floyd-Warshall all-pairs最短路徑算法。

七、Quicksort（快速排序）。

八、BFPRT 算法。

九、Knuth-Morris-Pratt字元串比對算法。

十、Union-find。

為了讓大家有更多的選擇，我再貼出其它幾種同樣經典但暫時未能排進上述榜單前十名的候選算法：

十一、Cooley-Tukey FFT算法。快速傅裡葉變換算法。關于傅裡葉變換算法的介紹，請參考此文：十、從頭到尾徹底了解傅裡葉變換算法、上，及十、從頭到尾徹底了解傅裡葉變換算法、下。

十二、linear programming，線性規劃。

十三、Dijkstra 算法。與上第五一樣，又一種最短路徑算法。具體介紹，請參考：二之續、徹底了解Dijkstra算法，和二之再續、Dijkstra 算法+fibonacci堆的逐漸c實作，及二之三續、Dijkstra 算法+Heap堆的完整c實作源碼。

十四、Merge Sort。歸并排序。

十五、Ford–Fulkerson算法。網絡最大流算法。

十六、輾轉相除法。

      在數學中，輾轉相除法，又稱歐幾裡得算法，是求最大公約數的算法，即求兩個正整數之最大公因子的算法。此算法作為TAOCP第一個算法被闡述，足見此算法被重視的程度。它是已知最古老的算法, 其可追溯至3000年前。輾轉相除法首次出現于歐幾裡得的《幾何原本》（第VII卷，命題i和ii）中，而在中國則可以追溯至東漢出現的《九章算術》。擴充的輾轉相除法則構造性地證明了，對任意整數a和b ，存在一對x、y使得 ax + by = gcd(a, b) 。

十七、RSA加密演算法。一種加密算法，日後再做詳細介紹。

十八、遺傳算法。可參考本人寫的關于GA 算法的這篇文章：七、遺傳算法 透析GA本質。

十九、最大期望（EM）算法。

    此算法入選資料挖掘領域十大經典算法。在統計計算中，最大期望（EM）算法是在機率（probabilistic）模型中尋找參數最大似然估計的算法，其中機率模型依賴于無法觀測的隐藏變量（Latent Variable）。最大期望經常用在機器學習和計算機視覺的資料聚類（Data Clustering）領域。最大期望算法經過兩個步驟交替進行計算，第一步是計算期望（E），利用對隐藏變量的現有估計值，計算其最大似然估計值；第二步是最大化（M），最大化在 E 步上求得的最大似然值來計算參數的值。M 步上找到的參數估計值被用于下一個

E 步計算中，這個過程不斷交替進行。

二十、資料壓縮

    資料壓縮是通過減少計算機中所存儲資料或者通信傳播中資料的備援度，達到增大資料密度，最終使資料的存儲空間減少的技術。資料壓縮在檔案存儲和分布式系統領域有着十分廣泛的應用。資料壓縮也代表着尺寸媒介容量的增大和網絡帶寬的擴充。

二十一、Hash函數

    Hash，一般翻譯做“散列”，也有直接音譯為“哈希”的，就是把任意長度的輸入（又叫做預映射， pre-image），通過雜湊演算法，變換成固定長度的輸出，該輸出就是散列值。關于hash表的詳細闡述，請參考此篇文章：十一、從頭到尾徹底解析Hash表算法。

二十二、Dynamic Programming（動态規劃）。關于動态規劃的粗略介紹，請參考此文：三、dynamic programming。

二十三、堆排序算法。

    堆排序算法作為一種快速穩定的算法，其平均時間複雜度（最壞也為）O（n*lgn）。當然，在實際應用中，一個實作的好的快速排序算法仍然要優于堆排序算法。不過，堆資料結構還可以作為高效的優先級隊列。對堆排序算法作簡單了解，可參考這：堆排序算法。

二十四、遞歸與回溯算法。此倆個算法，相信各位比較熟悉，在此不做贅述。  

二十五、最長公共子序列

    最長公共子序列，英文縮寫為LCS（Longest Common Subsequence）。其定義是，一個數列 S ，如果分别是兩個或多個已知數列的子序列，且是所有符合此條件序列中最長的，則 S 稱為已知序列的最長公共子序列。

動态規劃的一個計算最長公共子序列的方法如下：

    以兩個序列 X、Y 為例子：

設有二維數組 f[i][j] 表示 X 的 i 位和 Y 的 j 位之前的最長公共子序列的長度，則有：

      f[1][1] = same(1,1)

      f[i][j] = max{f[i-1][j-1]+same(i,j)，f[i-1][j]，f[i][j-1]}

    其中，same(a,b)當 X 的第 a 位與 Y 的第 b 位完全相同時為“1”，否則為“0”。

此時，f[i][j]中最大的數便是 X 和 Y 的最長公共子序列的長度，依據該數組回溯，便可找出最長公共子序列。

    該算法的空間、時間複雜度均為O(n2)，經過優化後，空間複雜度可為O(n)，時間複雜度為O(nlogn)。更多詳情，參見之前寫的一篇拙文（不過，鑒于寫的糟，日後會重寫）：三、dynamic programming。

二十六、紅黑樹的算法與實作

    關于紅黑樹，linux核心中有實作，本BLOG内也已經寫了6篇紅黑樹系列的文章。且，本BLOG内的此紅黑樹系列，總計六篇文章，是整個國内有史以來有關紅黑樹的最具代表性，最具完整性，最具參考價值的資料。詳情，請參考：五（續）、教你透徹了解紅黑樹，及紅黑樹的c++完整實作源碼。

二十七、A*搜尋算法。

    相對于BFS、Dijkstra 等算法，A*搜尋算法作為一種高效的最短路徑搜尋算法，如今，已得到日益廣泛的應用。初步了解A*搜尋算法的高效及與其它最短路徑算法的比較，請參考此文：一（續）、A*，Dijkstra，BFS算法性能比較及A*算法的應用。

二十八、圖像特征提取與比對之SIFT算法

    sift，尺度不變特征轉換，是一種電腦視覺的算法用來偵測與描述影像中的局部性特征，它在空間尺度中尋找極值點，并提取出其位置、尺度、旋轉不變量，此算法由 David Lowe 在1999年所發表，2004年完善總結。關于此算法，請參考如下，粗略介紹：九、圖像特征提取與比對之SIFT算法，利用第三方庫編譯過程：九（續）、sift算法的編譯與實作，c語言一步一步實作sift算法：九之再續：一步一步用c語言實作sift算法、上，及九之再續：教你一步一步用c語言實作sift算法、下。

候選經典算法一直在不斷增補中，估計最後能達到上100種。...

     還猶豫什麼列?快投上您寶貴的一票吧。每人可投多次票，隻要您認為哪個算法是最為經典的算法，您就在下面的評論裡寫上它的序号，及算法名稱。

    當然，如果上文中不曾出現你認為最經典的算法，你也可以寫在評論裡，為你鐘愛的它投上一票。而後我将考慮您的意見，把您鐘愛的算法也作為一種候選算法，添補上去。:D。

    最後，我們自己來做一份十大經典算法的排名榜單，也讓世界各地的人看看我們中國人的意見。怎麼樣，還猶豫什麼列，趕緊評論、趕緊投票吧...

    更新：由于諸多事情，未能抽空給各位投了票的朋友傳送本部落格全部博文集錦的檔案，若各位等不及日後待我一一傳送的話，還望各位移步至本人的資源下載下傳處：http://v_july_v.download.csdn.net/，下載下傳。那裡有本部落格所有任何一期的博文集錦檔案。見諒，多謝。 July、二零一一年十月二十四日淩晨。

本blog最新博文集錦第7期CHM檔案免積分下載下傳：http://download.csdn.net/detail/v_july_v/4463100。July、二零一二年一月十八日。

本BLOG版權聲明、即日生效：

    1、本人和CSDN對本BLOG内所有任何一切内容和文章，享有版權。如需轉載，請注明出處及作者本人。

    2、凡是轉載本BLOG内任何文章和内容的個人，或網站，一律不注明出處者，本人将永久追蹤、永久譴責、永久追究法律責任的一切權利。謝謝。July、二零一一年三月七日，即日起生效。

載自 ： 結構之法，算法之道。