有什麼理論複雜但是實現簡單的演算法？

12-29

Floyd最短路徑演算法

3個for嵌套，和冒泡排序幾乎一樣，但真正搞明白很不容易。

Miller–Rabin 素性檢測，幾行代碼

Splay Tree 可能是最簡單的平衡樹了

monad，算不上演算法吧

並查集應該是理論/實現比最大的演算法之一了吧

Isomap

Isomap是一個非線性降維的方法。實現不難（見Isomap Homepage），除去注釋、輸入參數判斷等，核心代碼也就100行左右。但原理涉及微分流形。

隱含狄利克雷分布（Latent Dirichilet Allocation）

http://zh.m.wikipedia.org/zh/隱含狄利克雷分布

反正我自己是理論看了很久沒看懂，網上找了個代碼看了一下，恍然大悟

KM演算法...二分圖帶權最優匹配演算法...

裡面涉及一個定理，我至今不知道如何證明...

隨機化快速排序。代碼就那麼一點，但是證明過程中各種情況討論，說實話，第一次看到這個演算法時間複雜度證明的時候驚呆了。

遞歸

LDA算一個，即潛在dirichlet分配，雖然說是比較簡單的生成模型，但是沒有學過貝葉斯方法的話去理解其數學過程還是挺費勁的。

演算法實現卻極其簡單，用統計模擬方法去訓練的話每一步只需要求一個條件概率再抽個樣就好了。

前面列出這些基礎演算法基本ACM能搞到銀牌水平的人都不會覺得理解困難，只能說可能因為大家演算法基礎不是很紮實，沒有把基礎問題想清楚就來思考更抽象的東西。

我覺得ML那些模型、演算法更難理解。不是說那些東西本身難理解，而是為什麼這樣做能work。

比如最基礎的，如何判斷一個問題是PAC learnable的，如果能，我們才有繼續研究這個問題的必要，如何能更機械化的給出判斷依據？

還有就是一些迭代的演算法，比如Gibbs Sampling為什麼收斂，SVD為什麼可以通過每次求當前最優Singular Value來使得全局誤差最小。

當然，這是一些可以理解的，還有一些數學上理解不了的，比如為什麼神經網路能work？

卡爾曼濾波

看了一圈竟然沒人說PID

樹狀數組，核心代碼寥寥幾行，但是卻不是那麼好理解。

PCA主成分分析，如果用octave, matlab, 或者numpy就是兩三行代碼: 求矩陣的協方差矩陣的特徵向量即可。但是理解其內涵是要學完整本線性代數的。

擬牛頓

後綴自動機

並查集

動態規劃，所有理論分析最終抽象成一個狀態轉移方程，代碼幾行實現，但是很不好想

公鑰加密演算法，比如rsa，橢圓曲線加密，代碼不難，但是原理比較複雜。