我們?yōu)槭裁匆伎妓惴╛數(shù)據(jù)分析師

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

Chinese teachers bring the art of maths to English schools

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

算法的定義

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

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

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

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

如果你是個碼農(nóng)：算法是一個計算過程，它接受一些輸入，并產(chǎn)生某些輸出。

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

但他們共同強(qiáng)調(diào)了一點(diǎn)：算法的不變式，即算法必須能夠讓人一步一步照著執(zhí)行。

算法的核心

算法是解決問題的辦法或法則。但解決一個問題不一定只有一種辦法，不同的辦法之間便有了好壞之分。對于解決同一個問題的不同算法，我們?nèi)绾伪容^它們的好壞呢？

能夠比較的東西當(dāng)然很多，如模塊性、正確性、可維護(hù)性、健壯性、友好性、簡易性、可擴(kuò)展性和可靠性等，但這些并不是算法設(shè)計與分析中最為關(guān)心的問題。但它們更加像是人類附加在算法上的外部屬性，因為它們通常依賴于使用或?qū)崿F(xiàn)算法的人員的其他方面素質(zhì)：理解力、表述力、編程水平、數(shù)據(jù)結(jié)構(gòu)的運(yùn)用與設(shè)計技巧等。

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

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

堆機(jī)器還是拼算法

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

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

原點(diǎn)：一對雌雄兔子

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

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

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

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

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

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

結(jié)語

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