源頭

　　“算法”的中文最早出現在中國漢代的數學名著《周髀算經》中。《周髀算經》卷上有：“數之法出于圓方。圓出于方，方出于矩。矩出于九九八十一”。意思是： 算數的方法都出于對圓、對方的計算，其中圓出于方(圓形面積=外接正方形x圓周率/4)，方出于矩(正方形源自兩邊相等的矩)，矩的計算出于九九八十一 (長乘寬面積的計算依自九九乘法表)。追溯回去，在春秋戰國時代，《九九乘法歌訣》已經開始流行起來。話說，自從卡梅倫被8×9等于多少問呆以后，英國教育部就開始聘請上海的小學數學老師赴英訓練小九九了……

Chinese teachers bring the art of maths to English schools

　　在西方，真正推動算法傳播的是一個居住在巴格達的阿拉伯人，Al Khwarizmi，他引進了印度更為先進的十進制數字系統。Al Khawarizmi展示了加、減、乘、除，乃至平方根和圓周率π的計算步驟。這些步驟的特點是：簡單、無歧義、有效、有窮步驟、正確。數百年后，當十進制阿拉伯數字系統在歐洲廣泛應用時，人們便創造出Al Khwarizmi 的拉丁化寫法“Algorithm”，來描述這種有規可循的數字計算行為。

　　算法的定義

　　究竟什么是算法呢，字面理解，就是計算的辦法或法則。這里的計算不單指加減乘除等算術運算，而是廣義的做任何事情的計算。辦法和法則，則意味著使用它可以解決眼前的問題。

　　就拿我們喜聞樂見的世界杯比賽來說，每四年一屆比賽的目的就是選出此時世界上踢球最牛掰的那個國家。在200多個國家里頭，如果用單循環聯賽賽制，也就是每個隊都必須和另外所有隊踢一場，以此決定本隊成績，假設每隔三天踢一場，最快也要600來天。怎么樣，累覺不愛吧，還是廣場舞來的更收放自如些。對于比賽組織者來說，明智的策略當然是先在幾個大洲里選出幾個屈指可數的球隊，然后大家聚在一起，一個月內論出高下，這時甚至還要再分成幾個組，每組最強的幾個隊才能突出重圍，踏上冠軍之路。

　　道理上來講，最好的球隊，無論哪種賽制，總是會脫穎而出的；而上述這種優中選優的方式，難度和開銷就降低許多了。上述過程有一個特定叫法：分治，也就是將一個大問題（尋找全世界的最佳球隊），分解成多個類型相同但規模更小的問題（尋找一個大洲的最佳球隊），如果小問題得以解決，那么大問題就更加容易解決了（各大洲最佳球隊PK一下，就知道世界冠軍的獎杯，花落誰家了）。這只是生活中眾多算法應用的一個例子，那么由事實到抽象拔高出來一個完備的字典式定義，對應用和分析者來說，其實無太多必要。事實上，算法的定義也因看待的角度不同而不同。

　　如果你是個哲學家：算法是解決一個問題的抽象行為序列。

　　如果你是個碼農：算法是一個計算過程，它接受一些輸入，并產生某些輸出。

　　如果你喜歡高大上：算法是解決一個精確定義的計算問題的工具。

　　但他們共同強調了一點：算法的不變式，即算法必須能夠讓人一步一步照著執行。

　　算法的核心

　　算法是解決問題的辦法或法則。但解決一個問題不一定只有一種辦法，不同的辦法之間便有了好壞之分。對于解決同一個問題的不同算法，我們如何比較它們的好壞呢？

　　能夠比較的東西當然很多，如模塊性、正確性、可維護性、健壯性、友好性、簡易性、可擴展性和可靠性等，但這些并不是算法設計與分析中最為關心的問題。但它們更加像是人類附加在算法上的外部屬性，因為它們通常依賴于使用或實現算法的人員的其他方面素質：理解力、表述力、編程水平、數據結構的運用與設計技巧等。

　　那么算法的核心或靈魂是什么呢？也許您已經可以猜到：速度。也就是其解決問題的速度。因為速度往往是區分可行和不可行方案的分水嶺。例如，一個讓人等上很多年才能運行結束的算法，就是再正確，也不會令我們滿意。從實際意義上看，這種算法的正確和不正確并無太大的本質區別。

　　如果一個算法在你的改進下，效率提高了成百上千倍，則當你坐在顯示屏前，所獲得的快感不會亞于很多其他的事情。

　　堆機器還是拼算法

　　說到提升速度，真壕們會不約而同的移步華強北，血拼內存處理器。然而，計算機速度的增長可以多大程度上解決一些簡單問題呢？我們來看一個經典的例子吧。

　　我們有一個描述兔子增長數量的模型：

　　原點：一對雌雄兔子

　　規律：每對兔子每月產下一對兔子，且一生只能生產兩次，而且第二次生產后老死。（我們這里假設產下的每對兔子都繼續正常繁衍，方舟子及果殼知識帝請繞路……）

　　如果定義在第n個月的兔子數量為F(n)，那么F(n)個兔子中包含這個月新生的兔子（也就是（第n-1月）兔子總數F(n-1)），和上個月的新生兔子數目（因為上個月的老兔子們這個月已經死掉了），即F(n-2)。所以F(n)=F(n-1)+F(n-2)，F(n)的序列叫做斐波那契序列。

　　那么我們就開始算F(n)吧，比如說你想知道第30個月時的兔子數量，那么F(30)=F(29)+F(28)，那么F(29)=F(28)+F(27)，我們一直分解下去，最后變成數數一共多少個F(0)了。我們寫段代碼，運行它，約朋友出去打個臺球，回來也許可以得到答案。若你眼光長遠，想知道第300個月時的兔子數量，那么你必須要尋找其它算法了。因為F(0)的數量太龐大了。這種天真遞歸解法，事實上要對F(0)進行指數級次的運算。聰明的你會進一步發現斐波那契數列是一個二階遞推數列，于是最后可以用對數級次運算搞定F(300)，這里細節省略，感興趣的話我們會在后續詳細討論。

　　問題是，在硬件性能愈加強悍的今天，大規模運算或者大數據的實踐者們，時常認為更快的算法也許沒有必要。那么我們來看斐波那契數的天真遞歸解法，它的時間復雜度為1.6的n次方，即計算F(n+1)的時間約是計算F(n)的1.6倍。按照摩爾定律計算性能每18個月翻倍的速度，每過一年，我們只能多計算一個未知的斐波那契數。

　　我們說IBM的Roadrunner 超級計算機性能為NEC的Earth Simulator的30倍，但這也僅僅意味著Roadrunner比后者在同樣的時間下以指數級復雜度多算7個數。但如果使用log(n)復雜度的算法，那么Roadrunner可多算10的30次方個斐波那契數。

　　所以，算法書其實不全是用來墊咖啡杯的……改進算法比起提升硬件速度的效果，還是很顯著的，不是嗎。

　　結語

　　對算法效率的追求，在任何場景中，都可以給你帶來意想不到的驚喜。對于產品的突破、開銷的降低、技術氣氛的凝聚，還有什么方式比思考與重視算法來的更加有效與唯美呢？

　　作者：華傲數據算法部

　　聲明：本文部分內容借鑒于T.H.Cormen等著《算法導論》與鄒恒明著《算法之道》，特此感謝與聲明。圖片源自網絡。