http://blog.163.com/pcteacher/blog/static/66585815200862183835111/
算法的力量（轉(zhuǎn)李開復）---適合計算機專業(yè)新生
算法的力量
2006年5月
算法是計算機科學領(lǐng)域最重要的基石之一，但卻受到了國內(nèi)一些程序員的冷落許多學生看到一些公司在招聘時要求的編程語言五花八門，就產(chǎn)生了一種誤解，認為學計算機就是學各種編程語言，或者認為，學習最新的語言技術(shù)標準就是最好的鋪路方法其實，大家被這些公司誤導了編程語言雖然該學，但是學習計算機算法和理論更重要，因為計算機語言和開發(fā)平臺日新月異，但萬變不離其宗的是那些算法和理論，例如數(shù)據(jù)結(jié)構(gòu)算法編譯原理計算機體系結(jié)構(gòu)關(guān)系型數(shù)據(jù)庫原理等等在開復學生網(wǎng)上，有位同學生動地把這些基礎(chǔ)課程比擬為內(nèi)功，把新的語言技術(shù)標準比擬為外功整天趕時髦的人最后只懂得招式，沒有功力，是不可能成為高手的
算法與我
當我在1980年轉(zhuǎn)入計算機科學系時，還沒有多少人的專業(yè)方向是計算機科學有許多其他系的人嘲笑我們說：知道為什么只有你們系要加一個科學，而沒有物理科學系或化學科學系嗎？因為人家是真的科學,不需要畫蛇添足，而你們自己心虛，生怕不科學，才這樣欲蓋彌彰 其實，這點他們徹底弄錯了真正學懂計算機的人（不只是編程匠）都對數(shù)學有相當?shù)脑煸劊饶苡每茖W家的嚴謹思維來求證，也能用工程師的務(wù)實手段來解決問題而這種思維和手段的最佳演繹就是算法
記得我讀博時寫的Othello對弈軟件獲得了世界冠軍當時，得第二名的人認為我是靠僥幸才打贏他，不服氣地問我的程序平均每秒能搜索多少步棋，當他發(fā)現(xiàn)我的軟件在搜索效率上比他快60多倍時，才徹底服輸為什么在同樣的機器上，我可以多做60倍的工作呢？這是因為我用了一個最新的算法，能夠把一個指數(shù)函數(shù)轉(zhuǎn)換成四個近似的表，只要用常數(shù)時間就可得到近似的答案在這個例子中，是否用對算法才是能否贏得世界冠軍的關(guān)鍵
還記得1988年貝爾實驗室副總裁親自來訪問我的學校，目的就是為了想了解為什么他們的語音識別系統(tǒng)比我開發(fā)的慢幾十倍，而且，在擴大至大詞匯系統(tǒng)后，速度差異更有幾百倍之多他們雖然買了幾臺超級計算機，勉強讓系統(tǒng)跑了起來，但這么貴的計算資源讓他們的產(chǎn)品部門很反感，因為昂貴的技術(shù)是沒有應(yīng)用前景的在與他們探討的過程中，我驚訝地發(fā)現(xiàn)一個O(n*m)的動態(tài)規(guī)劃（dynamic programming）居然被他們做成了O(n*n*m)更驚訝的是，他們還為此發(fā)表了不少文章，甚至為自己的算法起了一個很特別的名字，并將算法提名到一個科學會議里，希望能得到大獎當時，貝爾實驗室的研究員當然絕頂聰明，但他們?nèi)际菍W數(shù)學物理或電機出身，從未學過計算機科學或算法，才犯了這么基本的錯誤我想那些人以后再也不會嘲笑學計算機科學的人了吧!
網(wǎng)絡(luò)時代的算法
有人也許會說：今天計算機這么快，算法還重要嗎?其實永遠不會有太快的計算機，因為我們總會想出新的應(yīng)用雖然在摩爾定律的作用下，計算機的計算能力每年都在飛快增長，價格也在不斷下降可我們不要忘記，需要處理的信息量更是呈指數(shù)級的增長現(xiàn)在每人每天都會創(chuàng)造出大量數(shù)據(jù)（照片，視頻，語音，文本等等）日益先進的記錄和存儲手段使我們每個人的信息量都在爆炸式的增長互聯(lián)網(wǎng)的信息流量和日志容量也在飛快增長在科學研究方面，隨著研究手段的進步，數(shù)據(jù)量更是達到了前所未有的程度無論是三維圖形海量數(shù)據(jù)處理機器學習語音識別，都需要極大的計算量在網(wǎng)絡(luò)時代，越來越多的挑戰(zhàn)需要靠卓越的算法來解決
再舉另一個網(wǎng)絡(luò)時代的例子在互聯(lián)網(wǎng)和手機搜索上，如果要找附近的咖啡店，那么搜索引擎該怎么處理這個請求呢?
最簡單的辦法就是把整個城市的咖啡館都找出來,然后計算出它們的所在位置與你之間的距離,再進行排序,然后返回最近的結(jié)果但該如何計算距離呢？圖論里有不少算法可以解決這個問題
這么做也許是最直觀的，但絕對不是最迅速的如果一個城市只有為數(shù)不多的咖啡館,那這么做應(yīng)該沒什么問題,反正計算量不大但如果一個城市里有很多咖啡館,又有很多用戶都需要類似的搜索,那么服務(wù)器所承受的壓力就大多了在這種情況下,我們該怎樣優(yōu)化算法呢?
首先，我們可以把整個城市的咖啡館做一次預處理比如，把一個城市分成若干個格子(grid),然后根據(jù)用戶所在的位置把他放到某一個格子里，只對格子里的咖啡館進行距離排序
問題又來了，如果格子大小一樣，那么絕大多數(shù)結(jié)果都可能出現(xiàn)在市中心的一個格子里，而郊區(qū)的格子里只有極少的結(jié)果在這種情況下，我們應(yīng)該把市中心多分出幾個格子更進一步，格子應(yīng)該是一個樹結(jié)構(gòu)，最頂層是一個大格整個城市，然后逐層下降，格子越來越小，這樣有利于用戶進行精確搜索如果在最底層的格子里搜索結(jié)果不多，用戶可以逐級上升，放大搜索范圍
上述算法對咖啡館的例子很實用，但是它具有通用性嗎？答案是否定的把咖啡館抽象一下，它是一個點，如果要搜索一個面該怎么辦呢？比如，用戶想去一個水庫玩，而一個水庫有好幾個入口，那么哪一個離用戶最近呢？這個時候，上述樹結(jié)構(gòu)就要改成r-tree,因為樹中間的每一個節(jié)點都是一個范圍，一個有邊界的范圍（參考：http://www.cs.umd.edu/~hjs/rtrees/index.html）
通過這個小例子，我們看到，應(yīng)用程序的要求千變?nèi)f化，很多時候需要把一個復雜的問題分解成若干簡單的小問題，然后再選用合適的算法和數(shù)據(jù)結(jié)構(gòu)
并行算法：Google的核心優(yōu)勢
上面的例子在Google里就要算是小case了！每天Google的網(wǎng)站要處理十億個以上的搜索，GMail要儲存幾千萬用戶的2G郵箱，Google Earth要讓數(shù)十萬用戶同時在整個地球上遨游，并將合適的圖片經(jīng)過互聯(lián)網(wǎng)提交給每個用戶如果沒有好的算法，這些應(yīng)用都無法成為現(xiàn)實
在這些的應(yīng)用中，哪怕是最基本的問題都會給傳統(tǒng)的計算帶來很大的挑戰(zhàn)例如，每天都有十億以上的用戶訪問Google的網(wǎng)站，使用Google的服務(wù)，也產(chǎn)生很多很多的日志（Log）因為Log每分每秒都在飛速增加，我們必須有聰明的辦法來進行處理我曾經(jīng)在面試中問過關(guān)于如何對log進行一些分析處理的問題，有很多面試者的回答雖然在邏輯上正確，但在實際應(yīng)用中是幾乎不可行的按照他們的算法，即便用上幾萬臺機器，我們的處理速度都跟不上數(shù)據(jù)產(chǎn)生的速度
那么Google是如何解決這些問題的呢？
首先，在網(wǎng)絡(luò)時代，就算有最好的算法，也要能在并行計算的環(huán)境下執(zhí)行在Google的數(shù)據(jù)中心，我們使用的是超大的并行計算機但傳統(tǒng)的并行算法運行時，效率會在增加機器數(shù)量后迅速降低，也就是說，十臺機器如果有五倍的效果，增加到一千臺時也許就只有幾十倍的效果這種事倍功半的代價是沒有哪家公司可以負擔得起的而且，在許多并行算法中，只要一個結(jié)點犯錯誤，所有計算都會前功盡棄
那么Google是如何開發(fā)出既有效率又能容錯的并行計算的呢？
Google最資深的計算機科學家Jeff Dean認識到， Google 所需的絕大部分數(shù)據(jù)處理都可以歸結(jié)為一個簡單的并行算法：Map and Reduce（http://labs.google.com/papers/mapreduce.html） 這個算法能夠在很多種計算中達到相當高的效率，而且是可擴展的（也就是說，一千臺機器就算不能達到一千倍的效果，至少也可以達到幾百倍的效果）Map and Reduce的另外一大特色是它可以利用大批廉價的機器組成功能強大的server farm最后，它的容錯性能異常出色，就算一個server farm里面的機器down掉一半，整個farm依然能夠運行正是因為這個天才的認識,才有了Map and Reduce算法借助該算法，Google幾乎能無限地增加計算量，與日新月異的互聯(lián)網(wǎng)應(yīng)用一同成長
算法并不局限于計算機和網(wǎng)絡(luò)
舉一個計算機領(lǐng)域外的例子：在高能物理研究方面，很多實驗每秒鐘都產(chǎn)生幾個TB的數(shù)據(jù)量但因為處理能力和存儲能力的不足，科學家不得不把絕大部分未經(jīng)處理的數(shù)據(jù)丟棄掉可大家要知道，新元素的信息很有可能就藏在我們來不及處理的數(shù)據(jù)里面同樣的，在其他任何領(lǐng)域里，算法都可以改變?nèi)祟惖纳罾缛祟惢虻难芯浚涂赡芤驗樗惴ǘl(fā)明新的醫(yī)療方式在國家安全領(lǐng)域，有效的算法可能避免下一個911的發(fā)生在氣象方面，算法可以更好地預測未來天災的發(fā)生，以拯救生命
所以，如果你把計算機的發(fā)展放到應(yīng)用和數(shù)據(jù)飛速增長的大環(huán)境下，你一定會發(fā)現(xiàn)，算法的重要性不是在日益減小，而是在日益加強
給程序員的七個建議
（1）練內(nèi)功不要只花功夫?qū)W習各種流行的編程語言和工具，以及某些公司招聘廣告上要求的科目要把數(shù)據(jù)結(jié)構(gòu)算法數(shù)據(jù)庫操作系統(tǒng)原理計算機體系結(jié)構(gòu)計算機網(wǎng)絡(luò)，離散數(shù)學等基礎(chǔ)課程學好大家不妨試試高德納所著The Art of Computer Programming里的題目，如果你能夠解決其中的大部分題目，就說明你在算法方面有一定的功力了
（2）多實戰(zhàn)通過編程的實戰(zhàn)積累經(jīng)驗鞏固知識很多中國大學畢業(yè)生缺乏編程和調(diào)試經(jīng)驗；學習C語言，考試過關(guān)就算學會了；課題項目中，只要程序能夠編譯，運行，并且輸入輸出滿足要求就算了事這些做法是不行的寫程序的時候，大家必須多想想如何把程序?qū)懙酶泳珶捀咝Ц哔|(zhì)量建議大家爭取在大學四年中積累編寫十萬行代碼的經(jīng)驗我們必須明白的是：好程序員是寫出來的，不是學出來的
（3）求實干不要輕視任何實際工作，比如一些看似簡單的編碼或測試要不懈追求對細節(jié)一絲不茍的實干作風與敬業(yè)精神我發(fā)現(xiàn)不少程序員對于知識的掌握很膚淺，不求甚解，沒有好奇心，不會刨根問底比如，學會了C++，是否了解一個對象在編譯后，在匯編代碼中是如何被初始化的？這個對象的各個成員在內(nèi)存中是如何存放的？當一個成員函數(shù)被調(diào)用時，編譯器在匯編代碼中加入了哪些額外的動作？虛函數(shù)的調(diào)用是如何實現(xiàn)的? 這些東西恐怕在編程語言或編譯原理中都沒有詳細提到，只有通過踏實的實干才能真正掌握
（4）重視數(shù)學學習數(shù)學是思維的體操，數(shù)學無處不在學計算機至少要學習離散數(shù)學概率論布爾代數(shù)集合論和數(shù)理邏輯這些知識并不難，但是對你未來的工作幫助會很大 尤其當你對一些數(shù)學密集型的領(lǐng)域如視頻圖像處理等有興趣時，這些知識將成為你手中的利器
（5）培養(yǎng)團隊精神，學會與人合作今天的軟件工程早已經(jīng)不是一個人可以單獨操作的，而必須靠團隊合作才能成功不懂得合作的人是不能成大器的大家要多去尋找可以與人一起做項目的機會
（6）激勵創(chuàng)新意識，培養(yǎng)好奇心，不要死記硬背沒有掌握某種算法技術(shù)的根本原理，就不會有應(yīng)變和創(chuàng)新的能力想成為一位好程序員（其實從事任何一個行業(yè)都是如此），重要的是要養(yǎng)成鉆研，好奇，創(chuàng)新，動手，合作的優(yōu)秀習慣，不滿足于填鴨，不滿足于考試交差，不滿足于表象這不是學幾門課能夠一蹴而就的
（7）有策略地打工在不影響學業(yè)的前提下，尋找真正有意義的暑期工作或兼職去找一個重視技術(shù)的公司，在一個好的老板指導下完成真正會被用戶使用的程序不要急于去一個要你做頭而獨擋一面的地方，因為向別人學習才是你的目的找工作也是一樣，不要只看待遇和職銜，要挑一個你能夠?qū)W習的環(huán)境，一個愿意培養(yǎng)員工的企業(yè)，一個重視你的專業(yè)的公司最后，還要挑一個好老板
希望大家都能把握機會，養(yǎng)成好的學習習慣，把算法學精學透；希望大家都能有一個美好的未來！
該回復于2008-05-14 08:25:19被管理員刪除 The Art of Computer Programming Vol.1 (中文譯作計算機編程的藝術(shù)計算機程序設(shè)計技巧)--Basic Algorithms(基礎(chǔ)算法)
這部書被譽為20世紀最重要的20部著作之一，與Einstein的相對論并列，使計算機科學領(lǐng)域的權(quán)威著作全書共分5卷，目前已經(jīng)出版了3卷，這是它的第一卷基礎(chǔ)算法，包含了我們常用的算法及其相關(guān)數(shù)據(jù)結(jié)構(gòu)作者高德納(Donald E. Knuth)是美國Stanford大學計算機科學系的退休教授，在計算機科學領(lǐng)域享有崇高的威望
本文來自CSDN博客，轉(zhuǎn)載請標明出處：http://blog.csdn.net/zdl1016/archive/2009/09/27/4602750.aspx