哪些演算法曾讓你感覺醍醐灌頂？為什麼？

01-15

最初看到吳軍寫的《餘弦定理和新聞的分類》時，霎時震驚了，原來可以用這麼優美的數學語言解決如此複雜的問題；
後來研究等級排名方法，接觸到「Elo rating system」，亦頓時恍然大悟，如此簡約的公式可以計算實力差異。
鄙人見聞僅限互聯網方面，但請回答者不拘泥於行業差異，分享收穫。
演算法能附上詳細解釋會更好一些（方便外行人瀏覽）。

貝葉斯定理

比如這樣一個問題：你喜歡上一個人的概率，你覺得一個人某方面好的概率，你喜歡上一個人然後覺得這個人某方面好的概率，你覺得一個人某方面好然後喜歡上這個人的概率，這4個之間有什麼關係呢？

用數學語言表達：P(喜歡上一個人), P(覺得一個人某方面好), P(覺得這個人某方面好|喜歡上一個人) 和 P(喜歡上這個人|覺得一個人某方面好) 有什麼關係呢？

我們生活中遇到的很多概率其實都是條件概率/後驗概率(在某一條件下成立的事件的概率)，貝葉斯定理揭示了不同的條件概率之間的關係: )

一瞬間，感覺讓你發現了世界運行了某些奧秘

快速傅里葉變換。怎麼誇大這個演算法的重要性都不過分啊~這是現代信息社會的基石。

模擬退火，感覺寫好了目標函數似乎所有問題都能求出來近似全局最優解。

隱式馬爾科夫模型

快速排序演算法，一直覺得是經典中的經典

必須是快速傅里葉變換

TF/IDF演算法，簡單實用，作用非常大！

就知道遺傳演算法，感覺超有意思。

計算機學走路[越來越歡樂]

KMP非常優美，SIFT 圖像匹配演算法很強大，plsa語義相似度計算也讓我震撼，不過最讓我震撼的還是mathematica里的fullsimplify背後的演算法。

Fullsimplify這玩意能搞定很多人都搞不定的公式，我說的搞不定是指該問題本身人可以在三五步之內求解，但卻是很難求解的問題，例如某些三角函數的積分需要巧妙地作換元積分才能得解。

前面同學提的定理都好科普啊……我來提個小眾的~

個人預測Emmanuel Candes和Terrance Tao的Compressive Sensing會是21世紀前半葉信息科學領域提出的最牛逼的定理，沒有之一。

霍夫曼編碼

神經網路，這演算法太大，不過我覺得好經典啊

沿用了上千年的Euclid演算法和中國剩餘定理讓人肅然起敬。

費馬定理引申出的質數檢測同樣非常優美。

現代演算法中，五位大牛合作的BFPRT以及三位大牛的KMP都以其時間複雜度成為經典。

divide and conquer algorithm, 比如線性回歸的分治演算法，singular value decomposition的分治演算法，以及怎麼膜拜都不過分的FFT. 個人認為大數據時代把經典的演算法搞一個divide and conqueri版本是非常有必要的，這樣就能利用並行運算大大減少運算時間。

從思想上看，最深刻的是遞歸，以及求泛函極值的最小作用量。基於這兩種思想的演算法，比如快排、HMM中的Baum-Welch，都是精美的演算法，但背後的思想根基並非首創。動態規劃、蒙特卡洛類的演算法也屬此列。

此外，有「道法自然」意味的模擬退火、蟻群、遺傳、粒子群這些，思想方法上有創新，但是演算法設計上與神經網路、SVM、HMM相比，就略顯粗糙。

在技巧性上，KMP、Dijkstra、Viterbi這類演算法雖然經典，但都多少因為提出者的地位而被神化了。其實很多著名的演算法雖廣為流傳，但本質上都是個「先來後到」的問題。從精巧程度上看，很多演算法以及數據結構的設計之精妙都會讓人拍案叫絕，比如RSA、Fibonacci堆、紅黑樹等。還有一些經典問題突破上界的演算法與下界的證明，從設計到理論上的證明都是讓人讚歎的。

在技巧性上做到極致的演算法很多，只是有些不那麼出名而已。

但，上面所說的各種演算法，沒有一個比得上快速傅里葉變換(FFT)。從精巧程度上看，FFT可能相比與上述某些演算法略為遜色；但其作為信號處理的基石，影響之大遠超其它演算法。

最關鍵的是，FFT背後的思想深刻之餘，當屬首創。

歐拉公式本就是一個異常深刻的結論，「上帝創造的公式」此等美譽也是實至名歸。FFT通過歐拉公式將實數空間的運算問題映射至複數空間後，利用精心構造的數據在複數域中的性質來降低演算法複雜度，說是神來之筆也不為過。雖說SVM中的維度拓展帶來的線性可分也有類似空間變換的思想，但畢竟只是在同一個空間上變換，僅僅是維度上的改變。而FFT這種從實數空間到複數空間的變換，從而降低複雜度的思想，顯然更為深刻——揭示了在不同空間中問題複雜度可能不同這個秘密——最配得上「醍醐灌頂」四字。

希望有所幫助，歡迎討論。

BloomFilter 演算法

沒有人說page rank？

標準演算法集里，dijkstra的那個演算法，看了之後幾乎想去追星。

整數因子分解的Pallord-Rho演算法。差不多是O(n^0.25)效率，n是數的大小（所以對位數的話就指數級別了）

這個演算法本身其實到還不算醍醐灌頂。重點在其中的一個優化：在一個環中如果一個人以1的速度另一個人以2的速度（同向），那麼他們必然相遇。雖然簡單，但是異常漂亮^^

我覺得, 醍醐灌頂的, 當屬並查集和動態規劃. 並查集的路徑壓縮至今我認為是我看過里最簡潔最優美的設計. 而動態規劃, 在我心裡是一種很務實, 很有教育意義的演算法, "步步最優並非結果最優", "Ｔｒａｄｅ－ｏｆｆ", 等等．這兩個, 對我而言, 確實是醍醐灌頂的.