原文鏈接：http://zh.lucida.me/blog/on-learning-algorithms/
原文作者：Lucida
關(guān)于
嚴(yán)格來(lái)說(shuō)瑰排，本文題目應(yīng)該是 我的數(shù)據(jù)結(jié)構(gòu)和算法學(xué)習(xí)之路奥邮，但這個(gè)寫法實(shí)在太繞口——況且CS中的算法往往暗指數(shù)據(jù)結(jié)構(gòu)和算法（例如 算法導(dǎo)論 指的實(shí)際上是 數(shù)據(jù)結(jié)構(gòu)和算法導(dǎo)論），所以我認(rèn)為本文題目是合理的。
這篇文章講了什么？
我這些年學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)和算法的總結(jié)。
一些不錯(cuò)的算法書籍和教程饰序。
算法的重要性。
初學(xué)
第一次接觸數(shù)據(jù)結(jié)構(gòu)是在大二下學(xué)期的數(shù)據(jù)結(jié)構(gòu)課程规哪。然而這門課程并沒(méi)有讓我入門——當(dāng)時(shí)自己正忙于倒賣各種MP3和耳機(jī)求豫，對(duì)于這些課程根本就不屑一顧——反正最后考試劃個(gè)重點(diǎn)也能過(guò)，于是這門整個(gè)計(jì)算機(jī)專業(yè)本科最重要的課程就被傻逼的我直接忽略過(guò)去了。
直到大三我才反應(yīng)過(guò)來(lái)以后還要找工作——而且大二的折騰證明了我并沒(méi)有什么商業(yè)才能蝠嘉，以后還是得靠碼代碼混飯吃最疆，我當(dāng)時(shí)驚恐的發(fā)現(xiàn)自己對(duì)編程序幾乎一無(wú)所知，于是我給自己制訂了一個(gè)類似于建國(guó)初期五年計(jì)劃的讀書成長(zhǎng)計(jì)劃蚤告，其中包括C語(yǔ)言基礎(chǔ)努酸、數(shù)據(jù)結(jié)構(gòu)以及計(jì)算機(jī)網(wǎng)絡(luò)等方面的書籍。
讀書計(jì)劃的第一步是選擇書籍杜恰，我曾向當(dāng)時(shí)我覺(jué)得很牛的 “學(xué)長(zhǎng)” 和 “大神” 請(qǐng)教應(yīng)該讀哪些算法書籍获诈，”學(xué)長(zhǎng)”們均推薦算法導(dǎo)論，還有幾個(gè)”大神”推薦計(jì)算機(jī)程序設(shè)計(jì)藝術(shù)（現(xiàn)在我疑心他們是否翻過(guò)這些書）心褐，草草的翻了下這兩本書發(fā)現(xiàn)實(shí)在看不懂舔涎，但幸運(yùn)的是我在無(wú)意中發(fā)現(xiàn)了 豆瓣 這個(gè)神奇的網(wǎng)站，里面有很多質(zhì)量不錯(cuò)的書評(píng)逗爹，于是我就把評(píng)價(jià)很高而且看上去不那么嚇人的計(jì)算機(jī)書籍都買了下來(lái)——事實(shí)證明豆瓣要比這些”學(xué)長(zhǎng)”或是”大神”靠譜的多得多亡嫌。
數(shù)據(jù)結(jié)構(gòu)與算法分析——C 語(yǔ)言描述
數(shù)據(jù)結(jié)構(gòu)與算法分析——C 語(yǔ)言描述 是我學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的第一本書：當(dāng)時(shí)有很多地方看不懂，于是做記號(hào)反復(fù)看掘而；代碼看不明白挟冠，于是抄到本子上反復(fù)研讀；一些算法想不通袍睡，就把它所有的中間狀態(tài)全畫出來(lái)然后反復(fù)推演知染。事實(shí)證明盡管這種學(xué)習(xí)方法看起來(lái)傻逼而且效率很低，但對(duì)于當(dāng)時(shí)同樣傻逼的我卻效果不錯(cuò)——傻人用傻辦法嘛女蜈，而且這本書的課后題大多都是經(jīng)典的面試題目，以至于日后我看到 編程之美 的第一反應(yīng)就是這貨的題目不全是抄別人的么色瘩。
至今記得伪窖，這本書為了說(shuō)明算法是多么重要，在開篇就拿最大子序列和作為例子居兆，一路把復(fù)雜度從 O(N^3) 殺到 O(N^2) 再到 O(NlgN) 最后到 O(N)覆山，當(dāng)時(shí)內(nèi)心真的是景仰之情如滔滔江水連綿不絕，尼瑪為何可以這么屌泥栖，
此外簇宽，我當(dāng)時(shí)還把這本書里圖算法之前的數(shù)據(jù)結(jié)構(gòu)全手打了一遍，后來(lái)找實(shí)習(xí)還頗為自得的把這件事放到簡(jiǎn)歷里吧享，現(xiàn)在想想真是傻逼無(wú)極限魏割。
憑借這個(gè)讀書成長(zhǎng)計(jì)劃中學(xué)到的知識(shí)，我總算比較順利的找到了一份實(shí)習(xí)工作钢颂，這是后話钞它。
入門
我的實(shí)習(xí)并沒(méi)有用到什么算法（現(xiàn)在看來(lái)就是不停的堆砌已有的 API，編寫一堆自己都不知道對(duì)不對(duì)的代碼而已），在發(fā)現(xiàn)身邊的人工作了幾年卻還在和我做同樣的事情之后遭垛，我開始越來(lái)越不安尼桶。盡管當(dāng)時(shí)我對(duì)自己沒(méi)什么規(guī)劃，但我清楚這絕壁不是我想做的工作锯仪。
微軟的夢(mèng)工廠
[圖片上傳中泵督。。庶喜。（2）]
在這個(gè)搖擺不定的時(shí)刻小腊，微軟的夢(mèng)工場(chǎng) 成了壓倒駱駝的最后一支稻草，這本書對(duì)微軟亞洲研究院的描寫讓我下定了 “找工作就要這樣的公司” 的決心溃卡，然而我又悲觀的發(fā)現(xiàn)無(wú)論是以我當(dāng)時(shí)的能力還是文憑溢豆，都無(wú)法達(dá)到微軟亞研院的要求，矛盾之下瘸羡，我徹底推翻了自己”畢業(yè)就工作”的想法漩仙，辭掉實(shí)習(xí)，準(zhǔn)備考研犹赖。
考研的細(xì)節(jié)無(wú)需贅述队他，但至今仍清楚的記得自己在復(fù)試時(shí)驚奇且激動(dòng)的發(fā)現(xiàn)北航宿舍對(duì)面就是微軟西格瑪大廈，那種離理想又進(jìn)了一步的感覺(jué)簡(jiǎn)直爽到爆峻村。
算法設(shè)計(jì)與分析
我的研究生生涯絕對(duì)是一個(gè)反面典型——翹課麸折，實(shí)習(xí)，寫水論文粘昨，做水研究垢啼，但有一點(diǎn)我頗為自得——從頭到尾認(rèn)真聽了韓軍教授的算法設(shè)計(jì)與分析課程。
韓軍給我印象最深的有兩點(diǎn)：課堂休息時(shí)跑到外面和幾個(gè)學(xué)生借火抽煙张肾；講解算法時(shí)的犀利和毫不含糊芭析。
盡管韓軍從來(lái)沒(méi)有主動(dòng)提及，但我敢肯定 算法設(shè)計(jì)與分析基礎(chǔ) 就是他算法課程事實(shí)上的（de-facto）教材吞瞪，因?yàn)樗恼n程結(jié)構(gòu)幾乎和這本書的組織結(jié)構(gòu)一模一樣馁启。
如果 數(shù)據(jù)結(jié)構(gòu)與算法分析——C語(yǔ)言描述 是我的數(shù)據(jù)結(jié)構(gòu)啟蒙，那么韓軍的課程 算法設(shè)計(jì)與分析基礎(chǔ) 就是我的算法啟蒙芍秆，結(jié)合課程和書籍惯疙，我一一理解并掌握了復(fù)雜度分析、分治妖啥、減治霉颠、變治、動(dòng)態(tài)規(guī)劃和回溯這些簡(jiǎn)單但強(qiáng)大的算法工具荆虱。
算法引論
算法引論 是我這時(shí)無(wú)意中讀到的另一本算法書掉分，和普通的算法書不同俭缓，這本書從創(chuàng)造性的角度出發(fā)——如果說(shuō)算法導(dǎo)論講的是有哪些算法，那么算法引論講的就是如何創(chuàng)造算法酥郭。結(jié)合前面的 算法設(shè)計(jì)與分析基礎(chǔ)华坦，這本書把我能解決的算法問(wèn)題數(shù)量擴(kuò)大了一個(gè)數(shù)量級(jí)。
之后不从，在機(jī)緣巧合下惜姐，我進(jìn)入微軟亞洲工程院實(shí)習(xí)，離理想又近了一步椿息，自我感覺(jué)無(wú)限牛逼歹袁。
鞏固
在微軟工程院的實(shí)習(xí)是我研究生階段的一個(gè)非常非常非常重要的轉(zhuǎn)折點(diǎn)：
做出了一個(gè)還說(shuō)的過(guò)去的小項(xiàng)目。
期間百度實(shí)習(xí)面試受挫寝优，痛定思痛之下閱讀了大量的程序設(shè)計(jì)書条舔。
微軟的實(shí)習(xí)經(jīng)歷成為了我之后簡(jiǎn)歷上為數(shù)不多的亮點(diǎn)之一（本屌一沒(méi)成績(jī)，二沒(méi)論文乏矾，三沒(méi)ACM）孟抗。
這里就不說(shuō)1和3了（和本文題目不搭邊），重點(diǎn)說(shuō)說(shuō) 2钻心。
由于當(dāng)時(shí)組內(nèi)沒(méi)有特別多的項(xiàng)目凄硼，我負(fù)責(zé)的那一小塊又提前搞定了，mentor 便很慷慨的扔給我一個(gè) Kinect 和一部Windows Phone 讓我研究捷沸，研究嘛摊沉，自然就沒(méi)有什么 deadline，于是我就很雞賊的把時(shí)間三七開：七分倒騰 Windows Phone痒给，三分看書&經(jīng)典論文说墨。
然而一件事打斷了這段安逸的生活——
百度實(shí)習(xí)面試
基友在人人發(fā)百度實(shí)習(xí)內(nèi)推貼，當(dāng)時(shí)自我感覺(jué)牛逼閃閃放光芒苍柏，于是就抱著看看國(guó)內(nèi) IT 環(huán)境+虐虐面試官的變態(tài)心理投了簡(jiǎn)歷尼斧，結(jié)果在第一面就自己的師兄爆出翔：他讓我寫一個(gè) stof
（字符串轉(zhuǎn)浮點(diǎn)數(shù)），我磨磨唧唧半天也沒(méi)寫出完整實(shí)現(xiàn)序仙，之后回到宿舍趕快寫了一個(gè)版本發(fā)到師兄的郵箱突颊，結(jié)果對(duì)方壓根沒(méi)鳥我鲁豪。
這件事對(duì)我產(chǎn)生了很大的震動(dòng)——
原來(lái)自己連百度實(shí)習(xí)面試都過(guò)不去潘悼。
原來(lái)自己還是一個(gè)編程弱逼。
原來(lái)自己還是一個(gè)算法菜逼爬橡。
痛定思痛治唤，我開始了第二個(gè)”五年計(jì)劃”，三七開的時(shí)間分配變成了七三開：七分看書糙申，三分WP宾添。而這一階段的重點(diǎn)從原理（Principle）變成了實(shí)現(xiàn)（Implementation）——Talk is cheap, show me the code.
Elements of Programming
由于一直覺(jué)得名字里帶 “Elements of” 的都是酷炫叼炸天的書，所以我?guī)缀跏呛敛华q豫的買了這本 Elements of Programming（中譯本：編程原本），事實(shí)上這本書里的代碼（或者說(shuō) STL 的代碼）確實(shí)是：快缕陕，狠粱锐，準(zhǔn)，古龍高手三要素全齊扛邑。
C Interfaces and Implementation
百度面試被爆出翔的經(jīng)歷讓我意識(shí)到另一個(gè)問(wèn)題怜浅，絕大多數(shù)公司面試時(shí)都需要在紙上寫 C 代碼，而我自己卻很少用 C（多數(shù)情況用 C#）蔬崩，考慮到自己還沒(méi)牛逼到能讓公司改變面試流程的地步恶座，我需要提升自己編寫 C 代碼的能力（哪怕只是為了面試）。一頓 Google 之后沥阳，我鎖定了 C Interfaces and Implementation——另一本關(guān)于如何寫出狂炫酷帥叼炸天的C代碼的奇書跨琳，這里套用下 Amazon 的 評(píng)論：Probably the best advanced C book in existance。
嚴(yán)格來(lái)說(shuō)上面兩本書都不是傳統(tǒng)的算法書桐罕，因?yàn)樗鼈儌?cè)重的都不是算法脉让，而是經(jīng)典算法的具體實(shí)現(xiàn)（Implementation），然而這正是我所需要的：因?yàn)樗惴ǖ脑砦夷苷f(shuō)明白冈绊，但要給出優(yōu)雅正確簡(jiǎn)練的實(shí)現(xiàn)我就傻逼了侠鳄，哪怕是 stof
這種簡(jiǎn)單到爆的 “算法”。
依然是以前的傻逼學(xué)習(xí)方法：反復(fù)研讀+一遍又一遍的把代碼抄寫到本子上死宣，艱難的完成了這兩本書后伟恶，又讀了相當(dāng)數(shù)量的編程實(shí)踐（Programming Practice）書籍，自我感覺(jué)編程能力又大幅提升毅该，此外獲得新技能——紙上編碼博秫。這也成為了我之后找工作面試的三板斧之一。
應(yīng)用
說(shuō)老實(shí)話眶掌，自從本科實(shí)習(xí)之后挡育，我就一直覺(jué)得算法除了面試時(shí)能用用，其它基本用不上朴爬，甚至還寫了一篇當(dāng)時(shí)頗為自得現(xiàn)在讀起來(lái)極為傻逼的 文章 來(lái)黑那些動(dòng)不動(dòng)就”基礎(chǔ)”或”內(nèi)功”的所謂”大偶春”們，這里摘取一段現(xiàn)在看起來(lái)很傻逼但當(dāng)時(shí)卻覺(jué)得是真理的文字：
所以那些動(dòng)則就扯什么算法啊基礎(chǔ)啊內(nèi)功啊所謂的大牛們召噩，請(qǐng)閉上你的嘴母赵，條條大道通羅馬。算法并不是編程的前提條件具滴，數(shù)學(xué)也不會(huì)阻礙一個(gè)人成為優(yōu)秀的程序員凹嘲。至少在我看來(lái)，什么算法基礎(chǔ)內(nèi)功都是唬人的玩意构韵，多編點(diǎn)能用的實(shí)用的程序才是王道周蹭，當(dāng)然如果你是一個(gè)pure theorist的話就當(dāng)我什么都沒(méi)說(shuō)好了趋艘。
然而有意思的是，寫了這篇 文章 沒(méi)多久凶朗，鼓吹算法無(wú)用論的我自己做的幾個(gè)大大小小的項(xiàng)目全部用到了算法——我疑心是上天在有意抽我的臉瓷胧。
LL(k)
我在微軟實(shí)習(xí)的第一個(gè)項(xiàng)目做的是 代碼覆蓋率分析——計(jì)算 T-SQL 存儲(chǔ)過(guò)程的代碼覆蓋率。
簡(jiǎn)單的看了下 SQL Server 相關(guān)的文檔棚愤，我很快發(fā)現(xiàn) SQL Reporting Service 可以記錄 T-SQL 的執(zhí)行語(yǔ)句及行號(hào)抖单，于是行覆蓋（line coverage）搞定，但老大說(shuō)行覆蓋太 naive遇八，我們需要更實(shí)際的塊覆蓋（block coverage）矛绘。
閱讀了塊覆蓋的定義后，我發(fā)現(xiàn)我需要 對(duì)T-SQL 進(jìn)行語(yǔ)法分析刃永，在沒(méi)有找到一個(gè)好用的 T-SQL Parser 的情況下货矮，只能自己動(dòng)手搞一個(gè)：
比較奇詭的是，做這個(gè)項(xiàng)目時(shí)當(dāng)時(shí)我剛好把 ANTLR 作者的 Language Implementation Patterns（中譯本：編程語(yǔ)言實(shí)現(xiàn)模式）看了一半斯够，什么 LL(k) 啊 Packrat 啊 AST Walker 的概念啊正熱乎著呢囚玫。
于是，自己自己就照著 T-SQL 的官方 EBNF读规，三下五除二搞了一個(gè) T-SQL 存儲(chǔ)過(guò)程的 LL(k) Parser抓督，把代碼轉(zhuǎn)換成 AST，然后用一個(gè) External AST Walker 生成代碼塊覆蓋的 HTML 報(bào)表束亏，全部過(guò)程一周不到铃在。
老大自然是很滿意——我疑心他的原計(jì)劃是花兩三個(gè)月來(lái)完成這個(gè)項(xiàng)目，因?yàn)檫@個(gè)項(xiàng)目之后的兩個(gè)月我都沒(méi)什么活干碍遍，天天悠哉游哉定铜。
拼音索引
拼音索引是我接的一個(gè)手機(jī)應(yīng)用私活里的小模塊，用戶期待在手機(jī)文本框可以根據(jù)輸入給出智能提示：
比如說(shuō)輸入中國(guó)：
[圖片上傳中怕敬。揣炕。。（8）]
同樣东跪，輸入拼音也應(yīng)給出提示：
[圖片上傳中畸陡。。虽填。（9）]
中文匹配這個(gè)簡(jiǎn)單丁恭，但拼音匹配就得花時(shí)間想想了——懶得造輪子的我第一時(shí)間找到了微軟的拼音庫(kù)，但接下來(lái)我就發(fā)現(xiàn)微軟這個(gè)鳥庫(kù)在手機(jī)上跑不動(dòng)卤唉，研究了下發(fā)現(xiàn) WP7 對(duì) Dictionary 的 items 數(shù)量有限制涩惑，貌似是 7000 還是 8000 個(gè) item就會(huì)崩盤仁期，而標(biāo)準(zhǔn)漢字則有兩萬(wàn)多個(gè)桑驱，尼瑪竭恬。
痛罵MS坑爹+漢字坑爹之余，還是得自己擼一個(gè)庫(kù)出來(lái)：
首先把那兩萬(wàn)個(gè)漢字搞了出來(lái)熬的，排序痊硕，然后弄成一個(gè)超長(zhǎng)的字符串。
接下來(lái)用 Int16
索引了漢字所有的拼音（貌似500多個(gè)）押框。
再接下來(lái)用 Int64
建立漢字和拼音的關(guān)聯(lián)——漢字有多音字岔绸，所以需要把多個(gè)拼音 pack 到一個(gè) Int64
里，這個(gè)簡(jiǎn)單橡伞，位操作就搞定盒揉。
最后用二分+位移 Unpack，直接做到從漢字到拼音的檢索兑徘。
后來(lái)小測(cè)了下性能刚盈，速度是 MS 原來(lái)那個(gè)庫(kù)的五十倍有余，而代碼量只有 336 行挂脑。
用戶很 happy——因?yàn)槲疑訋О阉麤](méi)想到的多音字都搞定了藕漱，而且流暢的一逼。
我也很 happy崭闲，因?yàn)闆](méi)想到自己寫的庫(kù)居然比 MS 的還要快幾十倍肋联，同時(shí)小十幾倍。
從這個(gè)事情之后我變得特別理解那些造輪子的人——你要想想刁俭，如果你需要一個(gè)飛機(jī)輪子但市場(chǎng)上只有自行車輪子而且老板還催著你交工橄仍，你能怎么搞。
快速字符串匹配
前面提到在微軟實(shí)習(xí)時(shí)老大扔給我一個(gè) Windows Phone 讓我研究下牍戚，我當(dāng)時(shí)玩了玩就覺(jué)著不太對(duì)勁沙兰，找聯(lián)系人太麻煩。
比如說(shuō)找”張曉明”翘魄，WP 只支持定位到Z分類下——這意味著我需要在 Z 分類下的七十多個(gè)聯(lián)系人（姓張的姓趙的姓鐘的等等）里面線性尋找鼎天，每次我都需要滑動(dòng)四五秒才能找到這個(gè)張姓少年。
[圖片上傳中暑竟。斋射。。（10）]
這也太傻逼了但荤，本屌三年前的老破NOKIA都支持首字母定位罗岖，996->ZXM->張曉明，直接搞定腹躁，尼瑪一個(gè)新時(shí)代 Windows Phone 居然會(huì)弱到這個(gè)程度桑包。
搜了一下發(fā)現(xiàn)沒(méi)有好用的撥號(hào)程序，于是本屌就直接擼了一個(gè)支持首字母匹配的撥號(hào)程序出來(lái)扔到WP論壇里纺非。
結(jié)果馬上就有各種問(wèn)題出現(xiàn)——最主要的反映是速度太慢哑了，一些用戶甚至反饋按鍵有時(shí)要半秒才有反應(yīng)赘方。本屌問(wèn)了下他的通訊錄大小：大概 3000 多人弱左。
[圖片上傳中窄陡。。拆火。（11）]
吐槽怎么會(huì)有這么奇葩的通訊錄之余跳夭，我意識(shí)到自己的字符串匹配算法存在嚴(yán)重的性能問(wèn)題：讀取所有人的姓名計(jì)算出拼音，然后一個(gè)個(gè)的匹配——結(jié)果如果聯(lián)系人數(shù)量太多的話们镜，速度必然拙計(jì)币叹。
于是我就開始苦思冥想有沒(méi)有一個(gè)能夠同時(shí)搜索多個(gè)字符串的高端算法，以至于那兩天坐地鐵都在嘟囔怎么才能把這個(gè)應(yīng)用搞的快一些模狭。
最終還是在 Algorithms on Strings, Trees and Sequences 里找到了答案——確實(shí)有能夠同時(shí)搜索多個(gè)字符串的方法：Tries套硼，而且這本書還用足足一章來(lái)講怎么弄 Multiple string comparison，看得我當(dāng)時(shí)高潮迭起胞皱，直呼過(guò)癮邪意。
具體細(xì)節(jié)不多說(shuō)，總之換了算法之后反砌，匹配速度快了大約九十多倍雾鬼，而且代碼還短了幾十行。哪怕是有 10000 個(gè)聯(lián)系人宴树，也能在 0.1 秒內(nèi)搞定策菜，速度瓶頸就這樣愉快的被算法搞定。
Writing Efficient Programs
之后又做了若干個(gè)項(xiàng)目酒贬，多多少少都用到了”自制”的算法或數(shù)據(jù)結(jié)構(gòu)又憨，最奇詭的一次是寫一個(gè)電子書閱讀器里的分頁(yè)，我照著模擬退火（Simulated Annealing）的原理寫了一個(gè)快速分頁(yè)算法锭吨，事實(shí)上這個(gè)算法確實(shí)很快——但問(wèn)題是我都不知道為啥它會(huì)這么快蠢莺。
總之，算法是一種將有限計(jì)算資源發(fā)揮到極致的武器零如，當(dāng)計(jì)算資源很富余時(shí)算法確實(shí)沒(méi)大用躏将，但一旦到了效率瓶頸算法絕壁是開山第一刀（因?yàn)樗惴ú灰X嘛！要不還得換 CPU 買 SSD 升級(jí) RAM考蕾，肉疼盎霰铩！Ｐの浴）蚯窥。一些人會(huì)認(rèn)為這種說(shuō)法是有問(wèn)題，因?yàn)榫帉懶滤惴ǖ娜肆Τ杀居袝r(shí)比增加硬件的成本還要高——但別忘了增加硬件提升效率也是建立在算法是 Scalable的基礎(chǔ)上——說(shuō)白了還是得搞算法。
說(shuō)到優(yōu)化這里順帶提一下 Writing Efficient Programs——很難找到一本講代碼優(yōu)化的書（我疑心是自從 Knuth 說(shuō)了 過(guò)早優(yōu)化是萬(wàn)惡之源 之后沒(méi)人敢寫拦赠，萬(wàn)惡之源嘛巍沙，寫它干毛），注意這本書講的是代碼優(yōu)化——在不改變架構(gòu)矛紫、算法以及硬件的前提之下進(jìn)行的優(yōu)化。盡管書中的一些諸如變量復(fù)用或是循環(huán)展開的 trick 已經(jīng)過(guò)時(shí)牌里，但總體仍不失為一本好書颊咬。
提高
實(shí)習(xí)實(shí)習(xí)著就到了研二暑假，接下來(lái)就是求職季牡辽。
求職季時(shí)我有一種莫名的復(fù)仇感——尼瑪之前百度實(shí)習(xí)面試?yán)献颖荒銈兒诘穆祜w翔喳篇，這回求職老子要把你們一個(gè)個(gè)黑回來(lái)，尼瑪态辛。
現(xiàn)在回想當(dāng)時(shí)的心理實(shí)屬傻逼+幼稚麸澜，但這種黑暗心理也起了一定的積極作用：我絲毫不敢有任何怠慢，以至于在5月份底我就開始準(zhǔn)備求職筆試面試奏黑，比身邊的同學(xué)早了兩個(gè)月不止炊邦。
我沒(méi)有像身邊的同學(xué)那般刷題——而是繼續(xù)看書抄代碼學(xué)算法，因?yàn)槲艺J(rèn)為那些難得離譜的題面試官也不會(huì)問(wèn)——事實(shí)上也是如此熟史。
Algorithm Design Manual
[圖片上傳中馁害。。蹂匹。（14）]
因?yàn)楹芏?Coding Interview 的論壇都提到這本 紅皮書碘菜，我也跟風(fēng)搞了一本。事實(shí)證明限寞，僅僅是關(guān)于 Backtrack Template 那部分的描述就足以值回書價(jià)忍啸，更不用說(shuō)它的 Heuristics 和課后題。
編程珠璣&更多的編程珠璣
[圖片上傳中履植。计雌。。（15）]
[圖片上傳中玫霎。白粉。。（16）]
這兩本書就不用多介紹鼠渺，編程珠璣 和 更多的編程珠璣鸭巴，沒(méi)聽說(shuō)過(guò)這兩本書請(qǐng)自行面壁。前者偏算法理論拦盹，后者偏算法軼事鹃祖，前者提升能力，后者增長(zhǎng)談資普舆，都值得一讀恬口。
The Science of Programming
[圖片上傳中校读。。祖能。（17）]
讀到 編程珠璣 里面關(guān)于 Binary Search 的正確性證明時(shí)我大呼過(guò)癮歉秫，原來(lái)程序的正確性也是可以推導(dǎo)的，然后我就在那一章的引用里發(fā)現(xiàn) David Gries 的 The Science of Programming养铸⊙丬剑看名字就覺(jué)得很厲害，直接搞了一本開擼钞螟。
不愧為 編程珠璣 引用的書籍兔甘，讀完 The Science of Programming 之后，我獲得了證明簡(jiǎn)單代碼段的正確性 這個(gè)技能——求職面試三板斧之二鳞滨。
證明簡(jiǎn)單代碼段的正確性 是一個(gè)很神奇的技能——因?yàn)槊嬖嚂r(shí)大多數(shù)公司都會(huì)要求在紙上寫一段代碼洞焙，然后面試官檢查這段代碼，如果你能夠自己證明自己寫的代碼是正確的拯啦，面試官還能挑剔什么呢澡匪？
之后就是各種面試爽室，總之就是項(xiàng)目經(jīng)歷凌那、紙上代碼加正確性證明這三板斧，摧枯拉朽冠息。
進(jìn)化
求職畢業(yè)季之后就是各種 Happy碱蒙，Happy 過(guò)后我發(fā)現(xiàn)即將面臨另一個(gè)問(wèn)題：算法能力不足荠瘪。
因?yàn)閾?jù)說(shuō)以后的同事大多是 ACM 選手，而本屌從來(lái)沒(méi)搞過(guò)算法競(jìng)賽赛惩，而且知道的算法和數(shù)據(jù)結(jié)構(gòu)都極為基礎(chǔ)：像那些元胞自動(dòng)機(jī)哀墓、斐波那契堆或是線段樹這些高端數(shù)據(jù)結(jié)構(gòu)壓根只是能把它們的英文名稱 拼寫 出來(lái)，連用都沒(méi)用過(guò)喷兼，所以心理忐忑的一逼篮绰。
為了不至于到時(shí)入職被鄙視的太慘烈，加上自己一貫的算法自卑癥季惯，本屌強(qiáng)制自己再次學(xué)習(xí)算法：
算法（第四版）
[圖片上傳中吠各。。勉抓。（18）]
算法（第四版） 是我重溫算法的第一本書贾漏，盡管它實(shí)際就是一本 數(shù)據(jù)結(jié)構(gòu)的入門書，但它確實(shí)適合當(dāng)時(shí)已經(jīng)快把算法忘光的本屌——不為學(xué)習(xí)藕筋，只為重溫纵散。
這本書最大的亮點(diǎn)在于它把 Visualization 和 Formatting 做到了極致——也許它不是最好的數(shù)據(jù)結(jié)構(gòu)入門書，但它絕壁是我讀過(guò)的排版最好的書，閱讀體驗(yàn)爽的一逼伍掀；當(dāng)然這本書的內(nèi)容也不錯(cuò)掰茶，尤其是紅黑樹那一部分，我想不會(huì)有什么書會(huì)比此書講的更明白蜜笤。
6.851 Advanced Data Structures
[圖片上傳中濒蒋。。把兔。（19）]
Advanced Data Structures 是 MIT 的高級(jí)數(shù)據(jù)結(jié)構(gòu)教程沪伙，為什么會(huì)找到這個(gè)教程呢？因?yàn)镚oogle Advanced Data Structures 第一個(gè)出來(lái)的就是這貨垛贤。
這門課包含各種讓本屌世界觀崩壞的奇詭數(shù)據(jù)結(jié)構(gòu)和算法焰坪，它們包括但不限于：
帶 “記憶” 的數(shù)據(jù)結(jié)構(gòu)（Data Structure with Persistence）趣倾。
van Emde Boas（逆天的插入聘惦，刪除，前驅(qū)和后繼時(shí)間復(fù)雜度）儒恋。
o(1) 時(shí)間復(fù)雜度的的 LCA善绎、RMQ 和 LA 解法。
奇幻的 o(n) 時(shí)間復(fù)雜度的 Suffix Tree 構(gòu)建方法诫尽。
o(lglgn) 的 BST禀酱。
…
總之高潮迭起，分分高能牧嫉，唯一的不足就是沒(méi)有把它們實(shí)現(xiàn)一圈剂跟。
總結(jié)
從接觸算法到現(xiàn)在，大概七年：初學(xué)時(shí)推崇算法牛逼論酣藻，實(shí)習(xí)后鼓吹算法無(wú)用論曹洽，讀研后再被現(xiàn)實(shí)打回算法牛逼論。
怎么這么像辯證法里的肯定到否定再到否定之否定辽剧。
現(xiàn)在來(lái)看送淆，相當(dāng)數(shù)量的鼓吹算法牛逼論的人其實(shí)不懂算法的重要性——如果你連用算法解決 實(shí)際 問(wèn)題的經(jīng)歷都沒(méi)有，那你如何可以證明算法很有用怕轿？而絕大多數(shù)鼓吹算法無(wú)用論的人不過(guò)是低水平碼農(nóng)的無(wú)病呻吟——他們從未碰到過(guò)需要用算法解決的難題偷崩，自然不知道算法有多重要。
Peter Norvig 曾經(jīng)寫過(guò)一篇非常精彩的 SICP書評(píng)撞羽，我認(rèn)為這里把 SICP 換成算法依然適用：
To use an analogy, if algorithms were about automobiles, it would be for the person who wants to know how cars work, how they are built, and how one might design fuel-efficient, safe, reliable vehicles for the 21st century. The people who hate algorithms are the ones who just want to know how to drive their car on the highway, just like everyone else.
MIT 教授 Erik Demaine 則更為直接：
If you want to become a good programmer, you can spend 10 years programming, or spend 2 years programming and learning algorithms.
總而言之阐斜，如果你想成為一個(gè)碼農(nóng)或是熟練工（Code Monkey），你大可以不學(xué)算法诀紊，因?yàn)樗惴▽?duì)你確實(shí)沒(méi)有用智听；但如果你想成為一個(gè)優(yōu)秀的開發(fā)者（Developer），扎實(shí)的算法必不可少，因?yàn)槟銜?huì)不斷的掉進(jìn)一些只能借助算法才能爬出去的坑里到推。
以上考赛。
