在cstheory.stackexchange看到一個很有營養的帖子,發起人從《來自天書的證明》(Proofs from the Book)得到靈感，意思是，假如有上帝的話，上帝又有一本“算法天書”的話，那么這本算法書里面應該有哪些算法呢？NB而踴躍的跟貼者給出了讓人眼花繚亂的算法，每個算法都給出了鏈接，有的還給出了算法的框架。恰好我算法很薄弱，于是興起，簡單的翻譯一下，把那些跟貼的算法由熱門程度從高到低列下來，供自己參考。

0.Union-find 并查集算法

1.Knuth-Morris-Pratt?經典的KMP字符串匹配算法

2.Quicksort 快排，這里特別建議看原帖的Thread。

3.The algorithm of Blum, Floyd, Pratt, Rivest, and Tarjan 尋找第k大的數

4.Floyd-Warshall algorithm 弗洛伊德算法求最短路徑

5.Gentry's Fully Homomorphic Encryption Scheme 之前沒聽說過，好像是個加密算法

6.Miller-Rabin primality test 米勒-拉賓檢驗，測質數

7.AKS primality test AKS質數檢驗

8.constructing suffix arrays in linear time 線性時間內構造后綴數組……是這么翻譯吧？

9.Depth First Search 先深搜索

10.2-approximation for MAX-CUT 這個不知道怎么翻譯……，旅行商問題？

11.Cooley-Tukey FFT Algorithm 快速傅立葉變換

12.Huffman coding 哈夫曼編碼

13.Strassen's algorithm 施特拉森演算法 矩陣乘法

14.Grover's algorithm 量子算法，搜索亂序數據

15.Christofides' Algorithm 旅行商問題

16.Gale-Shapley stable marriage algorithm 穩定婚姻問題

17.Schwartz-Zippel lemma 多項式符號檢驗

18.linear programming 線性規劃

19.Schieber-Vishkin…? 最低共同祖先

20.Expander codes

21.Binary Search 二分查找

22.Robin Moser algorithm for solving a certain class of SAT instances

23.universal hashing 全域散列

24.Gaussian elimination 高斯消元法

25.reservoir sampling 水塘抽樣

26.Sieve of Eratosthenes 埃拉托斯特尼篩法

27.Knuth's Algorithm X

28.Horner's Algorithm 秦九韶算法

29.Dijkstra's algorithm 最短路徑算法

30. 為什么沒有viterbi, RANSAC,EM

From：http://bugway.appspot.com/?p=818801

http://www.cnblogs.com/skyseraph/

轉載于:https://www.cnblogs.com/skyseraph/archive/2010/12/15/1906741.html

總結

以上是生活随笔為你收集整理的算法天书的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。