這次我們來看看一本獨(dú)特的內(nèi)功心法膀值，也就是《算法設(shè)計(jì)》(Algorithm Design)钠右。這本書由Cornell大學(xué)兩位理論計(jì)算機(jī)科學(xué)領(lǐng)域的知名專家Kleinberg和Tardos撰寫，觀點(diǎn)很高但又具有極強(qiáng)的可讀性。
當(dāng)然，有人會(huì)爭辯這兩位作者所做的研究領(lǐng)域不是特別傳統(tǒng)的TCS嫩码，不過這屬于見仁見智的問題了。權(quán)當(dāng)八卦花邊來看罪既。
為何說這本書稱之為易筋經(jīng)呢铸题？主要是因?yàn)樗鼜念^到尾都在訓(xùn)練算法思維铡恕，不求全不貪多，主打算法思想回挽。最重要的是没咙，它步步深入猩谊，從若干典型問題著手讓你一點(diǎn)點(diǎn)提高姿勢水平千劈。
- 引言部分的幾個(gè)經(jīng)典問題可以說是開胃菜，然后作者就開始講算法分析的知識(shí)牌捷。需要指出的是墙牌，好多人沒有學(xué)會(huì)這個(gè)就妄談算法效率，這點(diǎn)非常不合適暗甥，好歹得明白漸近記號(hào)的意思才能評(píng)判算法吧喜滨。
- 接下來這本書開始討論圖，雖然出乎意料但又在情理之中撤防。因?yàn)楹芏喔呒?jí)算法都是關(guān)于圖的虽风，所以具備圖的知識(shí)是相當(dāng)重要的。另外寄月，作者在這章復(fù)習(xí)了數(shù)據(jù)結(jié)構(gòu)的知識(shí)辜膝，讓其學(xué)以致用。
- 貪心算法的最好例子就是Kruskal算法漾肮，而且可以關(guān)聯(lián)Union-Find的知識(shí)厂抖，因此作者在貪心算法這節(jié)詳細(xì)論述了相關(guān)算法，可謂一舉多得克懊。
- 分治算法以遞推式為綱忱辅，詳細(xì)講解了如何設(shè)計(jì)這類算法才能達(dá)到高效。當(dāng)然谭溉，算法分析知識(shí)的基礎(chǔ)在這里就發(fā)揮了重要作用墙懂，如果搞不清就難以找到好的劃分策略。
- 動(dòng)態(tài)規(guī)劃向來是難點(diǎn)中的難點(diǎn)扮念，作者用了很大篇幅討論這種算法設(shè)計(jì)策略垒在。當(dāng)然，又用圖問題來考慮扔亥，這反應(yīng)了寫作的完整性场躯。
- 這本書也詳細(xì)討論了網(wǎng)絡(luò)流，這是進(jìn)階算法必備的技能旅挤。
- 以上部分基本已經(jīng)涵蓋了算法設(shè)計(jì)策略踢关。但這本書在后半部分從難解問題出發(fā)，講解了近似算法和隨機(jī)算法粘茄，更能助你修煉內(nèi)力签舞。
當(dāng)然秕脓，秘籍雖好，還是要踏踏實(shí)實(shí)練習(xí)儒搭。若想投機(jī)取巧吠架，骨感的現(xiàn)實(shí)分分鐘會(huì)打臉的。正如本系列的主旨一樣搂鲫，一本書主義傍药，是要將這本書實(shí)實(shí)在在地看完，不明白的地方反復(fù)閱讀體會(huì)魂仍，方能成就自我拐辽。
由于國內(nèi)版權(quán)到期，《算法設(shè)計(jì)》的影印版和譯本已經(jīng)無法買到擦酌。不過不必?fù)?dān)心俱诸，據(jù)說這本書要在2018年推出第2版，期待它有新的改進(jìn)赊舶。它的競爭對(duì)手繁多睁搭，例如《算法導(dǎo)論》和《算法設(shè)計(jì)指南》，還有Sedgewick的《算法》第4版笼平。
不知道這本獨(dú)門秘籍是否會(huì)給我們帶來更多的驚喜园骆，拭目以待吧！
