標籤：

有哪些演算法驚艷到了你？

01-13

有哪些演算法當你剛接觸的時候，心裡有「居然還可以這樣算..」的想法？

Reservoir Sampling( Reservoir sampling )

這是我在今年求職過程中面試的時候被問到的，因為之前很少接觸Streaming的演算法，在聽到這個題目的時候被驚呆了，根本不能理解：

給一個Streaming的Data，未知長度，要求在Streaming結束後返回N個Data，且是等概率的。

在聽到這個問題的時候簡直驚呆了。如果Streaming長度已知為L，當然對於每一個Data，我生成一個N/L的概率即可。但是長度未知，也即概率未知，怎麼可能在Data來的時候判斷要不要保留這個Data，還能保證是等概率的……百思不得其解。

事後一番研究，才發現了這類演算法，演算法之簡單令人驚嘆：

首先保留前N個Data，對於後面來的Data以N/i的概率選擇是否保留，i為當前Data序號，保留的話在原來保留的N的Data中隨機剔除一個。最後返回這N的即可。

證明也很容易，奇妙得地方在於在計算概率的時候，出現了很長的，可以前後上下不斷約掉的分式。相互約去之後剩下的概率剛好是N/L，L為總長度。簡直美妙極了！

顯然這類演算法也非常有用，因為在實際問題中會出現大量需要在Streaming的數據中進行Sample，為下一步處理數據做準備的情形。而這竟然有一個O(L)的演算法，真是太驚艷了！

遺傳演算法，我知道，這是一大類演算法，但這演算法的思想著實讓人感到「驚艷」。

非常樸素的隨機迭代、通過Fitness函數篩選，模擬自然界的生物進化過程，就能解決很多問題。

北京的那個鳥巢體育館的鋼結構，就是用遺傳演算法迭代出來的，整體非常穩固。

日本的新一代高速列車車頭用遺傳演算法設計，節約了30%的能量。

美國的 X-Band 衛星上的天線用演化演算法設計，體積只有硬幣大小。

社會學研究上，有用演化演算法配合神經網路工作，也非常有趣。

遺傳演算法可能看起來很「暴力」，很「粗糙」，但是確實蘊含了很多的「可能性」，而且非常自然，非常容易理解，是非常美的演算法。

Angluin"s Learning Algorithm

假設用戶心裡想了一門正則語言，程序通過反覆詢問用戶某個句子是否屬於這門語言，經過有限步詢問可以構造出這門語言對應的DFA

既然是哪些，那我就多說幾個。

首先是KMP和與之相關的AC自動機（Aho-Corasick automaton，剛接觸以為是自動AC機），其思想和效率真的很驚艷。

然後是快速傅里葉變換（FFT），可以以nlog_{2}n 的複雜度計算n次多項式乘法。

其次是擴展歐幾里得演算法，數論題最常用演算法了，求乘法逆元、解一次不定方程超級好用，而且代碼很短很好記。

再次是快速冪取模演算法，理解之後代碼很好寫，而且效率很高。k階矩陣的n次方複雜度僅為k^{3}log_{2}n （不用strassen法加速的情況）。

最後再推薦一個好用但不完全嚴謹的演算法：Miller-Rabin素數測試演算法。非常快而且錯誤率很低啊！

自適應辛普森公式，對三點辛普森公式遞歸調用的積分演算法，代碼不到20行，解決所有一維定積分問題。

旋轉卡殼演算法可以在O（N）時間內求多邊形直徑。

-----------------------------------------------------------------------------上邊是正經回答，下邊是抖機靈

快速排序演算法也是非常好用的，#include&然後調庫是比賽中所有要排序的地方的處理方法，快速排序演算法讓我驚艷的地方是我去省圖書館看見兩個志願者需要把還回來的一堆書按順序入架，管理員大媽給他們教的時候說：「你先在這堆書里拉出一本來，把比它號小的扔到一邊，比它大的扔到另一邊，然後剩下兩堆繼續這樣整，這樣排的快！」這是我見識過最驚艷的演算法使用，沒有之一！

密碼分析里的差分攻擊演算法。

Diffie-Hellman的公鑰體系理論。如此的簡單，卻是如此的具有革命性的密碼演算法。

待續...

必須是數論變換,我不嫌丟人,看到這個演算法之前我根本不知道數論能幹嗎用.

一個基於數論的變換,把整數域變換到整數域,居然能和FFT形式上一致,還和定點DSP

結合得這麼好,連乘法器都不用,直接移位就能快速算卷積,驚了! 當時是在圖書館的一個

很破,舊的發黃的書上看到的,當時有一種摔下懸崖無意中發現了武功秘籍的感覺....

首先映入我腦海里的是 John Carmack 的Quake引擎里的一段代碼, 求一個數的平方根的倒數(注意是倒數,不是導數). John Carmack 是id software的創始人, 也是經典第一視角遊戲 Doom 和 Quake 的作者. 他對自己的Quake遊戲引擎進行開源, 極大地促進了整個3D遊戲行業前進的步伐. 連比爾蓋茨都將 Carmack 列為自己的崇拜對象!

一般能想到的辦法是:

1. 調用系統庫函數: sqrt, 然後再除1;

2. 二分法逼近 (之前Facebook的有道面試題即是);

3. 牛頓迭代法

而在Quake渲染引擎中, 有這麼一段代碼 (將其標號: #4 Quake InvSqrt 演算法):

float InvSqrt (float x){
float xhalf = 0.5f*x;
int i = *(int*)x;
i = 0x5f3759df - (i&>&>1);
x = *(float*)i;
x = x*(1.5f - xhalf*x*x);
return x;
}

如果有興趣的朋友自己去寫一個程序去測試, 發現上述4中方法的運算效率:

#4 &> #1 &> #3 &> #2.

借用一位朋友的照片:

看見Carmack代碼裡面的方法比起系統方法還快一倍以上, 而且實現方式短小且神奇. 其本質上也是使用了牛頓迭代法, 但是通過預先猜測的一個神奇數字 0x5f3759df, 來將迭代次數降到極限的一次 (另外通過整形數的移位來進一步加速). 這讓我不由得想到蘇聯飛機米格29引擎的暴力美學. 詳細解說看這個: Beyond3D - Origin of Quake3"s Fast InvSqrt()

P.S. 為什麼InvSqrt在Quake引擎中被重新實現? 這是因為3D變換過程中要涉及到大量的平方根翻轉操作 (比如3D向量的normalization), 所以對於這個函數的優化對於3D引擎的效率非常關鍵. 這也直接促使nVIDIA在最新的GPU的指令集中自帶"nrm"; 此命令來借用硬體加速直接完成3D向量的normalization操作.

類似的, Quake3里的開方函數源代碼:

double sqrt( double x ) {
float y;
float delta;
float maxError;

if ( x &<= 0 ) { return 0; } // initial guess y = x / 2; // refine maxError = x * 0.001; do { delta = ( y * y ) - x; y -= delta / ( 2 * y ); } while ( delta &> maxError || delta &< -maxError ); return y; }

同樣也是短小精妙. 另外附帶

Quake引擎架構分析: Quake Source Code Review

Quake3代碼分析: Quake 3 Source Code Review: Architecture

Quake代碼的GitHub頁: id-Software/Quake · GitHub

附帶我偶像John Carmack的一張照片 (祝Oculus在Facebook帝國的支持下欣欣向榮):

另外, 收到 @陳然 答案的啟發 (那個等概率選數問題我在Facebook的最後一面上剛好碰到, 因為之前面試根本沒有準備過, 導致自己最後面試上絞盡腦汁...), 所以我說一個自己對Facebook一道面試題經過多年沒事想想後的頓悟!!!

計算Fibonacci(斐波那契)數列的第n項: 這個之前在我的Facebook面試總結裡面有寫過, 可以遞歸也可以遞推, 這樣的複雜度是O(N), 也可以用矩陣相乘的演算法, 這樣可以O(LogN)的複雜度解決. 本來也就這樣作罷, 但是最近看了"星際穿越"之後, 突然頓悟到這個Fibonacci和星際穿越有異曲同工之妙:

在一維世界中只能通過公式 F(n) = F(n-1) + F(n-2) 來計算. 這時, 線性的演算法(O(N))是一維世界下的極限. 要如何加速呢? 類推到星際穿越中的話, 可行的方法就是升維, 從一維升到二維空間 (一維的F(n)升級到二維矩陣), 也就是說我們用升維將一維空間進行扭曲從而將距離縮短. 於是 [F(n), F(n-1)] = M^(n-1) [1, 1] ( M 是一個二維的常數矩陣). 這樣我們便可以更快地從 [1, 1] 到達 [F(n), F(n-1)]. 看! 多麼像一個數學世界裡面的時空穿越呀!

先就到這裡, 想到更多有趣的, 再進行補充.

來個最常接觸的演算法，我相信有80%的人都接觸過這個演算法，那就是dota里對各種概率型（比如暴擊）攻擊內置的演算法——偽隨機演算法 （Pseudo Random Distribution，簡稱PRD，不是需求文檔!）

暴擊真的看臉嗎？當然不是了，當你深刻理解了偽隨機演算法，我想你還是可以對暴擊進行一些人為干預的。這個時候就是你 dota 水平邁向另一個境界的時候了。

偽隨機跟真隨機有什麼區別呢？來舉個例子吧，假如劍聖的暴擊幾率為20%，那麼真隨機的情況下，系統隨機在1~100裡面生產一個整數，如果生成的整數小於等於20，那這次攻擊就判定為暴擊。這個時候就有可能出現連續5次攻擊全是跳劈，臉黑得選手可能連續10次攻擊也沒有一次暴擊。而極限的情況就是，你的BM或者PA可能一整場都在暴擊（卧槽，你丫開掛呢），或者你打完一整場都沒暴擊過一次（艹，簡直豬隊友啊）。而偽隨機呢，就是用來解決「減少連續性暴擊，減少連續性沒暴擊」這個問題。

還是拿劍聖20%暴擊概率舉例，這時候劍聖第一次攻擊暴擊的概率是5.57%，而下次的攻擊就會是11.14%，如果第二次還沒暴擊，那麼接下來的第三次攻擊的暴擊概率就提升到了16.71%，每次都加5.57%，直到第17次攻擊就會是100.26%的保證性暴擊（ (⊙o⊙)…，好像還真有臉黑的情況存在）。暴擊之後回到之前的5.57%，這樣在多次的攻擊後會形成個平均20%暴擊的幾率。

以下使用PRD機制的列表

  • 進攻類，暴擊、重擊、雙刀、漩渦
  • 防禦類，山嶺的皮膚，所有盾類

不受PRD機制控制的物品有

  • 碎骨錘，深淵之刀的暈，蝴蝶/天堂之戟的閃。

--------------------- 下面就是非常繁瑣的PRD機制了，不敢興趣的掠過就是------------------------

概率公式

p(N) = C * N

P(N) 表示在第N次攻擊之後某個動作發生得概率（下面還是以暴擊舉例吧），N表示第N次修正概率後得攻擊次數（最小值為1），C表示暴擊發生的初始概率以及每次攻擊之後概率的增量，是個簡單地線性關係。當N足夠多得時候，P（N）總會趨向於1。在以下的文章里，技能描述上的概率會以 P(E) 來代替，表示期望值。

PRD 常數C

以下有兩個表來描述常熟C。P(E)表示期望值，C是常數。MAX N表示 理論上疊加到100%暴擊之前的最後一次攻擊次數，舉個例子，如下表，比如的暴擊幾率是45%，C是0.24931，那麼N就是4，因為之前的連續4次攻擊都可以是普通攻擊，但第五次的時候，必定暴擊。

當然以上得理論值不是暴雪實際中應用的數值，實際應用是如下表

在上面表中可以發現，當暴擊幾率到一定值得時候，實際暴擊幾率就低於P(actual)就低於P(E),這後面就會涉及到暴擊收益遞減的問題，這裡就不深入討論了，必定dota裡面的暴擊好像也不是那麼好堆，像 WOW 裡面倒是可以討論一下。

再把兩個圖放一起對比，好好感受一下。常數C在在30%的時候實際值跟理論值還是很接近的，但是超過這個值以後，誤差就開始大了。

那麼引起這個概率偏差的原因是什麼呢？簡單歸納是由以下兩點因素造成的

1.常數C的有效位數。我們可以從上面的表格中看到，在實際運算中我們沒有採用無線有效位而是取了一個近似的5位小數點，造成了之後的誤差。如果是採取動態實時運算的C的話，這會在每一次攻擊動作的判定都會耗費非常多的CPU資源，因此選取了一種靜態的look up table。

2.所有的數值都是會天梯地圖準備的，而不是普通用戶自己編輯的地圖。我們可以發現天梯地圖裡面技能概率值最大的特殊攻擊是牛頭人的粉碎，25%，再回頭看看，在30%以下，實際技能觸發概率和期望概率是基本一致的，30%以後的C值都是在用之前的數據擬合出來的。而且說實話，暴雪粑粑目前也不在意這些情況。

AdaBoost haar Cascade 人臉檢測演算法，cvpr十年最佳論文

倍增演算法（用於構造後綴數組）。。（

int wa[maxn],wb[maxn],wv[maxn],ws[maxn];
int rank[maxn],height[maxn],sa[maxn];
bool cmp(int *r,int a,int b,int l)
{
return r[a]==r[b]r[a+l]==r[b+l];
}

void da(int *r,int *sa,int n,int m)
{
int i,j,p,*x=wa,*y=wb,*t;
for(i=0;i&=0;i--) sa[--ws[x[i]]]=i;

for(j=1,p=1;p&=j) y[p++]=sa[i]-j;
for(i=0;i&=0;i--) sa[--ws[wv[i]]]=y[i];
for(t=x,x=y,y=t,p=1,x[sa[0]]=0,i=1;i&

下面寫兩個個人覺得比較漂亮的演算法：A. 用於解決無向圖的最大切的Goemans-Williamson演算法。它把圖與高維幾何結合起來，思路很奇妙；B. 一個在數據流中找出現次數比較多的字元的演算法。

A. 最大切(max cut)

定義：給定一張連通的無向無權圖G = (V, E)，其中V是點集，E是邊集。如果(S, T)是V的一個劃分，即S cap T = emptyset且Scup T = V，我們稱S與T之間的邊為一組切(cut)，我們用(S, T)來表示這個切。最大切問題就是找到V的一個劃分(S^*, T^*)，使得得到的切所包含的邊的數量是最多的。

1. mathcal{O}(|V|)複雜度的2倍近似比（隨機）演算法

最大切是一個NP-hard的問題，因此不大可能在合理時間內精確地求解出最優解。如果我們允許最終得到的結果有一定誤差，那麼對於最大切問題，存在一個非常簡單的演算法：對每一個v in V，等概率隨機將其分到S和T中的一個。用 exttt{OPT}^R表示得到的切的大小，用 exttt{OPT}表示真正最大切的大小。那麼有：mathbb{E}[ exttt{OPT}^R] geq exttt{OPT} / 2。其中，mathbb{E}代表期望。證明如下。

證明：對每條邊(u, v)，(u, v)將出現在切中當且僅當u和v分別屬於S和T。定義隨機變數mathbb{I}_{(u,v)}：當uin S wedge vin T或者u in T wedge v in S時，mathbb{I}_{(u,v)} = 1；否則mathbb{I}_{(u,v)} = 0。易得：mathbb{E}[mathbb{I}_{(u,v)}] = 1 /2 。另外，由 extstyle{ exttt{OPT}^R = sum_{(u, v) in E}mathbb{I}_{(u,v)}}可以得到 extstyle{mathbb{E}[ exttt{OPT}^R] = sum_{(u, v) in E}mathbb{E}[mathbb{I}_{(u,v)}] = |E| / 2 geq exttt{OPT} / 2}。lacksquare

2. Goemans-Williamson演算法

個人覺得它比前兩個方法都巧妙：它不再單純從圖的角度來看最大切，而是將最大切與高維幾何結合起來。具體的，對於圖中的每個點v_i in V，演算法把v_i映射到n = |V|維空間中以原點為中心的單位球的一個點x_i上，即x_i in mathbb{R}^n且|x_i| = 1。這裡，|x_i|代表向量x_i的長度。如果(v_i, v_j) in E，那麼x_i與x_j之間也會有一條線段相連。如下圖。讓P是一個隨機生成的過原點的超平面。P將單位球切成兩半，也就是把所有x_i分成了兩部分，一部分在P的「上面」，另一部分在P的「下面」。這兩部分對應著原圖G的一個切，而切的大小就是被P切過的線段的數量。如下圖。通過為每個點v_i選擇適當的x_i，我們能使最終得到的切的大小 exttt{OPT}^{GW}滿足mathbb{E}[ exttt{OPT}^{GW}] geq 0.878cdot exttt{OPT}。這裡 exttt{OPT}^{GW}的隨機性來源於超平面P的選擇的隨機性。

如何選擇x_i？ 對於邊(v_i, v_j)，其對應的線段(x_i, x_j)的長度為|x_i - x_j|。直觀上，(x_i, x_j)的長度越長，其被P切到的概率就越大。因此，要使得總的被切到的線段儘可能多，我們應該使所有線段的長度儘可能長。所以，定義以下目標函數：

f(G, x_1, cdots, x_n) = sum_{(v_i, v_j) in E} frac{1}{4} |x_i - x_j|^2 = sum_{(v_i, v_j) in E} frac{1}{2} (1 - x_i^Tx_j)

f是所有線段的長度的平方和。這裡之所以用平方，主要是為了解決問題的方便。根據我們之前的討論，f應該儘可能大。因此，優化問題如下定義：

egin{align} ext{maximize} f(G, x_1, cdots, x_n) \ ext{subject to} |x_i| = 1 ext{ for } 1leq i leq n \ x_i in mathbb{R}^n ext{ for } 1 leq i leq n end{align}

這個問題是多項式可解的（這裡就不詳述了）。我們用f_{max}表示問題的最優值。

證明：這裡只給出證明的思路。我們主要需要證明兩個不等式：（1）f_{max} geq exttt{OPT}，即f_{max}是G的最大切的上界；（2）mathbb{E}[ exttt{OPT}^{GW}] geq 0.878f_{max}，即GW演算法返回的切的大小的期望不小於0.878f_{max}。這兩個不等式合起來可得：mathbb{E}[ exttt{OPT}^{GW}] geq 0.878 exttt{OPT}。

註：GW演算法中的圖引自"Geometric representation of graphs"這本書。

B. 在數據流中找Frequent Items

問題定義：用mathcal{S} = x_1, x_2, cdots, x_N，x_i in Sigma表示一個長度為N的數據流。其中，Sigma表示一個包含n個字元的符號表。我們用f_mathcal{S}(x)表示字元x在mathcal{S}的出現次數。Frequent Items問題的定義是：給定一個常數0<phi<0.5，找到所有在mathcal{S}中出現了至少phi N次的字元，即I(mathcal{S}, phi) = {x in Sigma mid f_mathcal{S}(x) geq phi N}。

易知：|I(mathcal{S}, phi)| leq 1 / phi；否則I(mathcal{S}, phi)中的字元在mathcal{S}中將出現大於phi N cdot 1 / phi = N次。

我們假設：N gg n gg 1 / phi；另外，我們也假設：mathcal{S}中的字元按照順序依次到來。因為內存非常小，我們無法將mathcal{S}保存下來。一個例子就是網路中的路由器，數據包會不斷地到達路由器，而路由器的內存非常小。

Karp提了一個只需要mathcal{O}(1 / phi)空間的演算法，而且可以保證演算法得到的結果I^+(mathcal{S}, phi)滿足：I(mathcal{S}, phi) subseteq I^+(mathcal{S}, phi)。

演算法：該演算法維護了1 / phi個計數器（佔用mathcal{O}(1 / phi)的空間），均初始化為0。在演算法中，我們將把空閑的計數器（即計數顯示為0）賦給新到來的沒有計數器的字元。當x_i到達的時候，有三種情況：

  • 如果x_i有計數器，其對應的計數器加1；
  • 如果x_i沒有計數器，但存在著空閑計數器（計數為0），那麼就把這個計數器賦給x_i，計數更新為1；
  • 如果前面兩種情況都不成立，那麼所有計數器都減少1。

當mathcal{S}所有元素都已到達並處理完時，返回所有計數器的當前所有者，記作I^+(mathcal{S}, phi)。

這裡，我們證明I(mathcal{S}, phi) subseteq I^+(mathcal{S}, phi)。假設x otin I^+(mathcal{S}, phi)。那麼在演算法中，x一共被消去了f_mathcal{S}(x)次。這裡的消去是指：要麼（1）x到來的時候正好屬於上面提到的第三種情況；要麼（2）x所持有的計數器因為其他字元的到來而減1。無論是哪一種情況，每次x被消去的時候，同時也有其他至少1 / phi個字元被消去。因此， 總的消去的字元至少為f_mathcal{S}(x)(1 / phi + 1) leq N。因此，f_mathcal{S}(x) < phi N Rightarrow x otin I(mathcal{S}, phi)。

如果我們允許讀取多一遍mathcal{S}，那麼我們可以精確求出I(mathcal{S}, phi)。

數據流的頻率估計問題：Karp的演算法也可以用來估計x在mathcal{S}中出現的次數。唯一的變動是當mathcal{S}中所有元素都已處理完的時候，如果一個字元x持有一個計數器，就把該計數器的值作為x的頻率估計值，記作c(x)；否則，c(x) = 0。可以保證，當計數器的個數為1 / phi時，c(x) leq f_mathcal{S}(x) leq c(x) + phi N。理由如下：對於字元x，其一共被消去了f_mathcal{S}(x) - c(x)次。由前面的證明有：f_mathcal{S}(x) - c(x) leq phi N Rightarrow f_mathcal{S}(x) leq c(x) + phi N 。

Monte Carlo Tree Search

說一個比較初等的.

我是數學專業的, 很長一段時間偏見的以為所謂編程演算法就是一些無聊又枯燥的東西, 本科的時候想嘗試把橢圓曲線加密演算法在電腦上實現一下, 然後發現上百位的冪直接求根本求不了, 然後某天發現了一個叫 exponentiation by square 的方法, 從此改變了我的偏見...

floyd 最短路演算法，簡潔。

中文無詞典分詞。不需要詞典，給我語料就能給你分詞。是不是聽起來就碉堡了！！！

http://www.matrix67.com/blog/archives/5044

finger tree 和 vEBT

以前做NLP相關的分類問題，使用N-Gram的模型來對語言進行建模。常常遇到一個問題就是維度太大而且稀疏，直接應用在LR、SVM等模型上，容易過擬合，training error和test error有巨大的gap。這非常的惱人，要不然就要標註一大推數據去解決它。除此之外，對於不同的任務需要去研究數據，看取怎樣n-gram feature更好，涉及不好的人工。

在2013的Mikolov的論文「Efficient Estimation of Word Representations in Vector Space」, 描述了一個方法，可以將文本轉換為一個固定長度的向量。第一次知道的時候非常的驚艷，做NLP的時候不用再去麻煩的處理feature了，全部embedding化就完了。

剛開始拿這個方法在微博數據上做了text classfication的實驗，將文本分詞後取他們的embedding然後直接求這些向量平均。喂進分類器後，實驗結果已經比較接近傳統的N-Gram方法。

這個演算法出來的結果還有個非常有名的性質：向量之間是有關係的。 比如：

皇帝 - 男 = 皇后 - 女

通過這個性質我還弄了個同義詞獲取的功能，讓用戶在系統上任意輸入一個詞然後系統自動可以給出其類似的詞。

除了其應用上面的強大，訓練一個word2vec模型也是非常簡單而且高效的。

從一個神經網路的模型出發

WX20170522-193517.png

到Mikolov使用CBow和Skip-gram的方法來高效訓練。你要做的僅僅是隨機初始化所有詞的向量，然後迭代的使用周圍的詞來預測中心詞，通過神經網路的後項傳播進行訓練。直接訓練收斂。這樣每個詞的向量就有了。

這種神級的方法出來後，才有了火的不行的deep learning在NLP領域的應用。

補充：

感謝 @馬宇峰 的提醒，為了表達更準確，我把之前的「推薦演算法」改為「基於用戶的協同過濾演算法」

1.基於用戶的協同過濾演算法：使用餘弦函數來找到，比如某一商品的選擇方面，和你匹配的用戶，從而根據這個用戶的選擇來給你進行推薦商品

2. 蒙特卡洛演算法，神一般的統計模擬方法。第一次接觸的時候，就看到了那個估計圓周率的經典例子，圓周率竟然可以通過落入嵌入某個正方形中的1／4圓範圍內的點的概率估算出來，頓時覺得腦洞大開

引用維基百科裡面的一段話來描述就是：

蒙特卡洛方法可用於近似計算圓周率：讓計算機每次隨機生成兩個0到1之間的數，看以這兩個實數為橫縱坐標的點是否在單位圓內。生成一系列隨機點，統計單位
圓內的點數與總點數，（圓面積和正方形面積之比為PI:4，PI為圓周率），當隨機點取得越多時，其結果越接近於圓周率（然而準確度仍有爭議：即使取10
的9次方個隨機點時，其結果也僅在前4位與圓周率吻合）。

下圖來自維基百科：

我也來列一些不是那麼常見的演算法或者演算法設計思想。這些演算法我已熟知多年，但是回憶起第一次見到的場景仍然是胸中激蕩。

1. The power of power of 2

下午跟同事吃飯的時候正好聊到一個問題：假設你站在一個足夠長的走廊上，在這個走廊的某個位置有一個物品你需要去找到它，請問你應該選擇什麼樣的搜索策略。這個問題的關鍵在於你不知道目標是在你的左邊還是右邊，為了保證在線性複雜度內找到它，你可以先向左走1步，回到起點，再向右走1步，再回到起點並向左走2步，……，就這樣按照 1，2，4，8，...的等比數列進行搜索，一直到發現目標為止。（雖然在這裡2的等比並非是最優的，但這個不重要。）

很簡單的思想對吧，但不知當面試時遇到「請問怎麼檢測一個鏈表是否有環」的問題時你是否能舉一反三呢？我反正是沒想到，但是有人想到了，這就是Brent"s Algorithm http://en.wikipedia.org/wiki/Cycle_detection 。這個演算法與所謂的標準解法（快慢指針，或者叫做Floyd"s Algorithm）一樣優秀（如果不是更好的話，）請務必隨身裝備，這樣下次若有面試官還問你就可以好好秀一把：這個問題我有三種解法blablabla...然後把Brent"s Algorithm丟出去糊他一臉。

2. Fractional Cascading

http://en.wikipedia.org/wiki/Fractional_cascading，史上最酷炫的演算法設計技巧沒有之一。首先名字就取得非常騷包，其次，還十分有療效。利用它可以一次性解決計算幾何中的一大票問題，比如Orthogonal Range Query，Multiple List Query，Point Location，等等。

3. Rabin Flips a Coin

https://rjlipton.wordpress.com/2009/03/01/rabin-flips-a-coin/。求平面上最近點對的O(nlogn)演算法大家都知道，因為演算法導論上有寫。但是O(n)的演算法就沒那麼多人了解了。Rabin"s Algorithm是隨機演算法中的一個典型代表，看上去直接粗暴，甚至比算導上那個分治法還要簡單得多，為什麼某名其妙就O(n)了呢？

4. Indirection

5. Amortizing - Deamortizing

以後再寫……

tarjan，O(n)算強聯通分量。

並查集。

推薦閱讀：

※回族是如何形成的？
※你認為民歌「土」嗎？
※如何評價巴哥犬這種狗？
※你潛意識裡有哪些比較變態的念頭或想法？
※蘋果中國公司官方網站上有過哪些奇怪或錯誤的中文表述？

TAG:演算法 | 數據挖掘 | 調查類問題 | 計算機科學 |