簡(jiǎn)介《算法導(dǎo)論》第四版是麻省理工學(xué)院出版社出版的計(jì)算機(jī)科學(xué)經(jīng)典教材由四位國(guó)際知名學(xué)者合著被全球眾多高校選為算法課程指定教材。資源面向計(jì)算機(jī)專業(yè)學(xué)生、考研者及從業(yè)工程師系統(tǒng)講解算法的設(shè)計(jì)、分析與實(shí)現(xiàn)方法無(wú)論是課程學(xué)習(xí)、考研復(fù)習(xí)還是技術(shù)面試準(zhǔn)備都能從中獲得扎實(shí)的理論支撐與解題思路。全書(shū)從基礎(chǔ)概念到高級(jí)專題循序漸進(jìn)涵蓋排序與選擇、堆與快速排序、線性時(shí)間排序、數(shù)據(jù)結(jié)構(gòu)、圖算法、動(dòng)態(tài)規(guī)劃、貪心算法、回溯算法、分治算法、近似算法及NP完全理論等核心主題并對(duì)時(shí)間復(fù)雜度與空間復(fù)雜度分析、矩陣乘法含斯特拉森算法等進(jìn)階內(nèi)容做了深入闡述書(shū)中配有大量實(shí)踐習(xí)題與案例分析幫助讀者在設(shè)計(jì)、分析和實(shí)現(xiàn)層面完整掌握算法知識(shí)。資源為單個(gè)PDF文件共1個(gè)文件大小19.64MB內(nèi)容清晰完整適合長(zhǎng)期收藏與反復(fù)查閱。目前已有1247人學(xué)習(xí)瀏覽是系統(tǒng)學(xué)習(xí)算法、備戰(zhàn)面試或開(kāi)展科研的高質(zhì)量參考。1. 算法導(dǎo)論第四版PDF從啃不動(dòng)到能吃透的經(jīng)典大部頭如果只允許我在算法領(lǐng)域保留一份 PDF我會(huì)選《算法導(dǎo)論 第四版》。它既不是刷題攻略也不是速成講義而是一份把插入排序、紅黑樹(shù)、動(dòng)態(tài)規(guī)劃、最大流一直延伸到機(jī)器學(xué)習(xí)聚類(lèi)的完整算法地圖。準(zhǔn)備面試補(bǔ)手撕代碼、讀研開(kāi)始接觸理論、或者工作多年想系統(tǒng)回爐的人都能在這里找到自己缺的那一塊。第一次翻開(kāi)的人容易被厚度嚇退但真正的難點(diǎn)不是書(shū)太厚而是不知道按什么順序讀以及讀到哪一步該停下來(lái)驗(yàn)證。這份 PDF 給出的是一套完整的原理、習(xí)題和偽代碼剩下的問(wèn)題只有一個(gè)怎么把它變成自己的東西。2. 算法導(dǎo)論第四版值得讀嗎第四版改了什么適合哪種讀法2.1 第四版最直觀的變化章節(jié)地圖和配套都變了第四版在結(jié)構(gòu)上做了一個(gè)很聰明的調(diào)整把機(jī)器學(xué)習(xí)、并行算法、在線算法這些貼近現(xiàn)代工程的話題分別獨(dú)立成章放在全書(shū)的專題部分。目錄里能看到第 25 章單獨(dú)講二分圖匹配穩(wěn)定婚姻問(wèn)題和匈牙利算法拿到了完整篇幅第 26 章講 fork-join 并行第 27 章講在線算法第 33 章干脆把聚類(lèi)、乘性權(quán)重、梯度下降這些內(nèi)容寫(xiě)成了“機(jī)器學(xué)習(xí)算法”一章。對(duì)老讀者來(lái)說(shuō)這種變化意味著以前要拼湊多個(gè)章節(jié)才能理解的主題現(xiàn)在有了一條完整的推導(dǎo)線索。除了章節(jié)調(diào)整第四版在閱讀體驗(yàn)上的改動(dòng)也值得說(shuō)。全書(shū)插圖統(tǒng)一換成了彩色版本231 幅圖不再是一團(tuán)灰分治遞歸樹(shù)、紅黑樹(shù)旋轉(zhuǎn)、最大流殘存網(wǎng)絡(luò)這些原本依賴想象力的內(nèi)容現(xiàn)在顏色能直接幫你區(qū)分不同的路徑與節(jié)點(diǎn)狀態(tài)。每一章末尾保留了星號(hào)標(biāo)記帶 ★ 的小節(jié)和習(xí)題明確面向研究生層次普通人可以整段跳過(guò)而不影響主線。這種把“本科基礎(chǔ)”和“科研進(jìn)階”分開(kāi)的做法對(duì)自學(xué)者非常友好我第一次用的時(shí)候甚至覺(jué)得有點(diǎn)感動(dòng)——終于不用在入門(mén)階段跟研究生難度的證明死磕了。配套資源也比前幾版完整。全書(shū)配有 931 道練習(xí)題和 162 道綜合題每個(gè)章節(jié)末尾的 Problems 經(jīng)常能引出教材正文沒(méi)講透的新結(jié)論這些題比 Exercises 更值得反復(fù)做。官方配套網(wǎng)頁(yè)公布了一部分習(xí)題的參考解答不是全部但足夠用來(lái)驗(yàn)證自己的思路對(duì)不對(duì)。要注意的是它始終是教材不是題庫(kù)不要指望靠刷它的題來(lái)應(yīng)付在線評(píng)測(cè)平臺(tái)的算法題它的定位是幫你建立完整的算法設(shè)計(jì)和分析能力而不是訓(xùn)練刷題手感。2.2 學(xué)生、面試準(zhǔn)備者、工程師三種讀法面向不同目標(biāo)的人這本書(shū)的打開(kāi)方式差異很大。我見(jiàn)過(guò)不少人拿起書(shū)就從第 1 頁(yè)開(kāi)始背三周后卡在漸近記號(hào)后面全盤(pán)放棄也見(jiàn)過(guò)把整本書(shū)當(dāng)字典查的工程師每次遇到不熟悉的數(shù)據(jù)結(jié)構(gòu)就翻對(duì)應(yīng)章節(jié)反而用得得心應(yīng)手。下面這張表可以當(dāng)作選路線的起點(diǎn)人群優(yōu)先章節(jié)主要產(chǎn)出在讀學(xué)生1-5、8-9、14-16、20-24課堂作業(yè)、考試證明、復(fù)雜度分析能力面試準(zhǔn)備者2、6-13、15、22-23、32手撕代碼、復(fù)雜度推導(dǎo)、邊界處理工程實(shí)踐者10-13、17-19、21、26-27把偽代碼翻譯成可維護(hù)的實(shí)現(xiàn)學(xué)生的讀法相對(duì)固定第一學(xué)期覆蓋基礎(chǔ)、排序和數(shù)據(jù)結(jié)構(gòu)第二學(xué)期覆蓋動(dòng)態(tài)規(guī)劃、貪心和圖算法。每一章的 Problems 都要?jiǎng)邮肿鲆驗(yàn)樗鼈儽?Exercises 更接近真實(shí)問(wèn)題經(jīng)常要綜合三四個(gè)算法才能解出來(lái)。做不完也沒(méi)關(guān)系但至少每章挑兩道最難的硬啃這個(gè)過(guò)程比讀十頁(yè)正文都長(zhǎng)本事。面試準(zhǔn)備者的讀法不需要從第 1 頁(yè)開(kāi)始。先讀第 2 章插入排序、第 4 章分治、第 6-7 章堆排序與快速排序、第 12-13 章二叉搜索樹(shù)與紅黑樹(shù)再攻第 15 章動(dòng)態(tài)規(guī)劃里的 LCS 和矩陣鏈、第 22-23 章單源與多源最短路、第 32 章 KMP。讀的過(guò)程中必須把偽代碼實(shí)現(xiàn)成真實(shí)代碼配合在線評(píng)測(cè)平臺(tái)按主題刷題。重點(diǎn)不是把書(shū)讀完而是把高頻考點(diǎn)對(duì)應(yīng)的章節(jié)嚼碎手撕快排、堆排、二分、鏈表反轉(zhuǎn)、二叉樹(shù)遍歷、DP 狀態(tài)轉(zhuǎn)移方程這些在面試?yán)锍霈F(xiàn)的頻率遠(yuǎn)高于 B 樹(shù)刪除和線性規(guī)劃。工程實(shí)踐者的讀法更偏功利把第 10-13 章哈希表與平衡樹(shù)吃透存儲(chǔ)引擎和緩存設(shè)計(jì)背后的原理都在這里第 17 章的區(qū)間樹(shù)和動(dòng)態(tài)順序統(tǒng)計(jì)在業(yè)務(wù)查詢場(chǎng)景里經(jīng)常能用上第 18 章 B 樹(shù)是數(shù)據(jù)庫(kù)索引的地基第 26-27 章并行與在線算法對(duì)應(yīng)多核調(diào)度和實(shí)時(shí)系統(tǒng)附錄的求和、矩陣、概率部分不要當(dāng)作正文讀遇到看不懂的推導(dǎo)回來(lái)查就夠。那么什么時(shí)候不適合讀這本書(shū)如果你只有兩周準(zhǔn)備面試或者只需要完成一個(gè)很小的編程任務(wù)直接看精簡(jiǎn)的講義或刷題總結(jié)效率更高。這本書(shū)的價(jià)值在“長(zhǎng)期復(fù)利”第一遍建立骨架第二遍填充細(xì)節(jié)第三遍開(kāi)始能自己推導(dǎo)變體算法。真正能把它用起來(lái)的人都有不止一次從頭翻閱的經(jīng)歷。3. 拿到PDF后怎么讀三個(gè)月路線圖與自檢方法3.1 一條可以照抄的三個(gè)月閱讀規(guī)劃我見(jiàn)過(guò)太多人拿到這份 PDF 后的第一反應(yīng)是從第 1 頁(yè)開(kāi)始線性閱讀然后把書(shū)合上再也沒(méi)打開(kāi)。更有效的做法是給自己定一個(gè)“以產(chǎn)出為驗(yàn)收標(biāo)準(zhǔn)”的路線圖每一周結(jié)束時(shí)都能交出一份東西。以下是我整理的一條經(jīng)過(guò)實(shí)踐驗(yàn)證的路線適合從零補(bǔ)算法基礎(chǔ)的人和剛?cè)雽W(xué)的學(xué)生參考。時(shí)間段主題內(nèi)容驗(yàn)收產(chǎn)出第 1 周第 1-3 章算法基礎(chǔ)與漸近記號(hào)能默寫(xiě)插入排序并解釋最壞情況復(fù)雜度第 2-3 周第 4 章分治與主定理能畫(huà)出歸并排序遞歸樹(shù)寫(xiě)出主定理三個(gè) case第 4-5 周第 6-9 章堆、快排、線性時(shí)間排序手寫(xiě)堆排序、快排、計(jì)數(shù)排序并通過(guò)對(duì)拍測(cè)試第 6 周第 10-11 章基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)和哈希實(shí)現(xiàn)鏈地址法哈希表和處理沖突第 7-8 周第 12-13 章二叉搜索樹(shù)與紅黑樹(shù)實(shí)現(xiàn) BST 增刪查畫(huà)出紅黑樹(shù)插入修復(fù)流程第 9-10 周第 14-15 章動(dòng)態(tài)規(guī)劃與貪心手寫(xiě)鋼條切割、LCS、Huffman 編碼第 11 周第 16 章攤還分析用勢(shì)能法分析動(dòng)態(tài)表擴(kuò)張第 12-13 周第 20 章BFS、DFS、拓?fù)?、?qiáng)連通用鄰接表實(shí)現(xiàn)四種圖算法第 14 周第 21 章最小生成樹(shù)用并查集優(yōu)化 Kruskal 算法第 15 周第 22-23 章最短路算法實(shí)現(xiàn) Bellman-Ford 和 Dijkstra跑通帶權(quán)圖如果已經(jīng)讀過(guò)一遍可以直接從第 12 周開(kāi)始把精力集中在圖算法和動(dòng)態(tài)規(guī)劃的進(jìn)階實(shí)現(xiàn)上。如果只準(zhǔn)備面試參考上一章的面試路線圖不需要走完這條完整路線。每周結(jié)束時(shí)用三個(gè)標(biāo)準(zhǔn)自檢能不能合上書(shū)寫(xiě)出本周涉及的全部偽代碼能不能對(duì)著復(fù)雜度公式解釋為什么是這個(gè)增長(zhǎng)階能不能拿一個(gè)五元素的小例子手工走一遍算法并追蹤每步狀態(tài)。三個(gè)標(biāo)準(zhǔn)都滿足才算過(guò)關(guān)否則寧可慢一周也不要把問(wèn)題沉淀到下個(gè)主題。盲目趕進(jìn)度是自欺欺人后半程你會(huì)發(fā)現(xiàn)前面略過(guò)的內(nèi)容全部會(huì)回來(lái)找你。拿到 PDF 的第一步建議先做一件事給文件加書(shū)簽。把八個(gè)大部分的書(shū)名設(shè)為父層每章章名設(shè)為子層第 3 章和第 4 章單獨(dú)標(biāo)注成“數(shù)學(xué)工具”和“主定理”。絕大多數(shù) PDF 閱讀器都支持書(shū)簽導(dǎo)出后面回查某個(gè)算法時(shí)不用再靠滾動(dòng)條在幾百頁(yè)里亂翻。提示第 3 章的漸近記號(hào)內(nèi)容當(dāng)作參考手冊(cè)處理需要時(shí)回來(lái)查不要在第一遍就花一周死磕形式定義。3.2 用“手動(dòng)走一遍”的方法吃透插入排序讀第 2 章插入排序時(shí)掃一遍偽代碼很容易產(chǎn)生“我懂了”的錯(cuò)覺(jué)合上書(shū)一寫(xiě)就露餡。我常用的方法很簡(jiǎn)單把 INSERTION-SORT 翻譯成能在本地單步執(zhí)行的腳本拿一個(gè)五元素?cái)?shù)組手動(dòng)走一遍每一輪外層循環(huán)結(jié)束后把數(shù)組的狀態(tài)打印出來(lái)和書(shū)上的圖解對(duì)照。下面這個(gè)模板是 0 基數(shù)組的 Python 實(shí)現(xiàn)def insertion_sort(a): # a: 待排序數(shù)組原地修改不返回值 for j in range(1, len(a)): # j 是當(dāng)前要插入的元素位置 key a[j] # 取出當(dāng)前鍵值 i j - 1 # 從 j-1 開(kāi)始往前掃描 while i 0 and a[i] key: # 把比 key 大的元素逐個(gè)右移 a[i 1] a[i] i - 1 a[i 1] key # 在空出來(lái)的位置寫(xiě)回 key return a邏輯說(shuō)明偽代碼里數(shù)組下標(biāo)從 1 開(kāi)始翻譯到 Python 時(shí)外層循環(huán)從第二個(gè)元素開(kāi)始內(nèi)層 while 根據(jù) 0 基邊界改成i 0。key 暫存當(dāng)前要插入的值所有比 key 大的元素右移一位循環(huán)結(jié)束后把 key 寫(xiě)回空位。整個(gè)算法只用了常數(shù)個(gè)額外變量空間復(fù)雜度 O(1)屬于原地排序。參數(shù)說(shuō)明函數(shù)接受任意可比較元素的列表整數(shù)、浮點(diǎn)數(shù)、字符串都能排但如果列表里混了不同類(lèi)型比較時(shí)會(huì)拋 TypeError。最容易翻車(chē)的邊界條件是while i 0漏掉等號(hào)那會(huì)讓第一個(gè)元素永遠(yuǎn)不參與比較排序從第二步就開(kāi)始出錯(cuò)。另外注意穩(wěn)定性的細(xì)節(jié)比較條件是a[i] key而不是相等元素不會(huì)被交換位置所以插入排序是穩(wěn)定排序這個(gè)特點(diǎn)在工程里有時(shí)會(huì)被特意利用。手動(dòng)走一遍的方法我一般配合紙筆做紙上畫(huà)四列表格分別是數(shù)組快照、j、key、i每走完一輪 while 就更新一次。五元素的例子走完你對(duì)為什么插入排序最壞是 O(n2)、最好能到 O(n) 的理解會(huì)比只看書(shū)上的推導(dǎo)深刻得多。這種“手算追蹤”的方式對(duì)后面讀紅黑樹(shù)、Dijkstra、KMP 一樣有效算是讀算法導(dǎo)論最值得養(yǎng)成的習(xí)慣之一。3.3 讀分治章節(jié)時(shí)用主定理反向推一遍遞歸樹(shù)第 4 章是全書(shū)第一個(gè)真正的數(shù)學(xué)高地覆蓋了替換法、遞歸樹(shù)、主定理最后還給了 Akra-Bazzi 遞推的一般形式。對(duì)大多數(shù)讀者來(lái)說(shuō)最實(shí)用的是主定理T(n) 2T(n/2) Θ(n) 屬于 case 2結(jié)果是 Θ(n log n)T(n) 2T(n/2) Θ(n2) 屬于 case 3結(jié)果是 Θ(n2)。常見(jiàn)誤區(qū)是只看 f(n) 和 n^(log_b a) 的大小忽略了主定理要求的是“多項(xiàng)式意義上的大于或小于”差一個(gè) n^ε 因子就可能不適用。讀這一節(jié)時(shí)建議把遞歸樹(shù)畫(huà)三遍第一遍跟著圖例畫(huà)一個(gè)九節(jié)點(diǎn)的樹(shù)第二遍拿歸并排序畫(huà) n16 的完整分層第三遍把遞歸樹(shù)每一層的代價(jià)寫(xiě)成求和式最后算出總和。這個(gè)過(guò)程走完你會(huì)自然理解為什么歸并排序是 n log n 而不是 n2。耳朵聽(tīng)一百遍“l(fā)og n 來(lái)自遞歸深度”不如自己畫(huà)一棵樹(shù)來(lái)得踏實(shí)。第 4.7 節(jié) Akra-Bazzi 是帶星號(hào)的進(jìn)階內(nèi)容處理主定理三個(gè) case 都不適用的變體遞歸式。本科生和面試選手可以直接跳過(guò)但如果你之后要讀研究論文見(jiàn)到形式奇怪的遞歸式時(shí)能認(rèn)出“這是 Akra-Bazzi 可解的”就夠了。讀分治章節(jié)時(shí)還有一個(gè)容易被忽略的點(diǎn)Strassen 矩陣乘法。不要只背那個(gè)七次乘法的結(jié)論重點(diǎn)看它是怎么通過(guò)“減少乘法次數(shù)、增加加法次數(shù)”來(lái)改變遞推式的這種思路在后來(lái)的 FFT 和快速矩陣求逆里會(huì)反復(fù)出現(xiàn)。4. 讀算法導(dǎo)論的常見(jiàn)翻車(chē)現(xiàn)場(chǎng)四個(gè)高頻坑與排查思路4.1 坑一按目錄線性通讀三個(gè)月卡在第三章現(xiàn)象不少讀者拿到 PDF 后信心滿滿地立 flag每周讀一章。第一周順利翻完第 1 章第二周開(kāi)始接觸插入排序到第 3 章漸近記號(hào)就發(fā)現(xiàn)每頁(yè)都是新符號(hào)一遍看不懂進(jìn)度徹底卡死后面整個(gè)學(xué)習(xí)計(jì)劃崩盤(pán)。原因第 3 章和第 4 章是全書(shū)數(shù)學(xué)符號(hào)的集散地O、Ω、Θ、o、ω 加上求和、對(duì)數(shù)的性質(zhì)全擠在一起。這些內(nèi)容不是看過(guò)一遍就結(jié)束的“導(dǎo)論”而是后續(xù)每章都要回頭查閱的工具集。線性通讀恰好把工具章節(jié)當(dāng)成入門(mén)章節(jié)來(lái)啃失敗不在于書(shū)難而在于閱讀順序不合理。解決第一遍閱讀只保留以具體算法為核心的章節(jié)比如第 2 章的插入排序、第 6-9 章的排序全家桶遇到不認(rèn)識(shí)的記號(hào)再回第 3 章查對(duì)應(yīng)定義。漸近記號(hào)會(huì)在后續(xù)章節(jié)里反復(fù)出現(xiàn)看得多了自然就熟了。附錄 A-D 的求和、集合、概率、矩陣也一樣當(dāng)手冊(cè)用不要逐頁(yè)精讀。我自己的習(xí)慣是在書(shū)簽里把第 3 章命名為“查符號(hào)”需要時(shí)直接跳過(guò)去找定義。4.2 坑二偽代碼下標(biāo)從 1 開(kāi)始翻譯成代碼后邊界全亂現(xiàn)象照著第 2 章的 INSERTION-SORT 寫(xiě) Python翻譯完一跑發(fā)現(xiàn)第一個(gè)元素總是丟照搬第 6 章 HEAPSORT 的下標(biāo)關(guān)系數(shù)組一直越界堆排序結(jié)果亂成一團(tuán)。原因偽代碼用 A[1..n] 表示數(shù)組循環(huán)經(jīng)常寫(xiě)for j 2 to n而 Python、Java、C 全是 0 基數(shù)組。翻譯時(shí)如果只把循環(huán)邊界做了簡(jiǎn)單的減一處理內(nèi)部訪問(wèn)就會(huì)全面錯(cuò)位。堆排序更典型偽代碼里left 2*i、right 2*i1是 1 基下的關(guān)系換成 0 基必須變成left 2*i1、right 2*i2漏掉這個(gè)換算整個(gè)堆的父子關(guān)系都是亂的。解決翻譯前先確定索引基準(zhǔn)。我的做法是先把偽代碼里所有A[k]在草稿紙上換成A[k-1]再對(duì)循環(huán)邊界做整體平移最后補(bǔ)三個(gè)邊界測(cè)試空數(shù)組、單元素?cái)?shù)組、含重復(fù)元素的數(shù)組。這三種情況都能通過(guò)不代表正確但能排除一大半低級(jí)錯(cuò)誤。堆排序還要注意另一個(gè)隱藏點(diǎn)偽代碼里A.heap-size和A.length是兩個(gè)不同概念前者表示堆的有效長(zhǎng)度排序過(guò)程中會(huì)逐步縮小翻譯成 Python 后堆的有效長(zhǎng)度要單獨(dú)用一個(gè)變量維護(hù)不能直接用len(a)。4.3 坑三以為看懂證明就能寫(xiě)出代碼結(jié)果手生得可怕現(xiàn)象每一章的推導(dǎo)都能順暢地跟下來(lái)紅黑樹(shù)的插入修復(fù)、Dijkstra 的松弛操作、KMP 的失敗函數(shù)都覺(jué)得自己看懂了。過(guò)兩周回頭連紅黑樹(shù)刪除有幾種情況都記不清更別說(shuō)手撕代碼。原因閱讀是被動(dòng)跟隨寫(xiě)代碼是主動(dòng)構(gòu)建。跟隨敘述路徑時(shí)大腦完成的是“識(shí)別”而不是“生成”。算法學(xué)習(xí)的檢驗(yàn)標(biāo)準(zhǔn)不是“看懂了”而是“合上書(shū)之后還能不能準(zhǔn)確復(fù)現(xiàn)”。這兩者之間的差距比大多數(shù)人想象中大得多。解決每章結(jié)束后合上書(shū)寫(xiě)三樣?xùn)|西算法要維持的不變式、偽代碼框架、一個(gè)五元素手工執(zhí)行跟蹤。寫(xiě)完再打開(kāi)書(shū)對(duì)照只標(biāo)記差異點(diǎn)不要重新讀整章。差異點(diǎn)通常集中在邊界變量、循環(huán)不變式和終止條件上而這些正是后續(xù)面試和工程實(shí)現(xiàn)最容易丟分的位置。如果發(fā)現(xiàn)自己寫(xiě)不出來(lái)不要沮喪這是正常的信號(hào)說(shuō)明這一章需要重新過(guò)一遍而不是翻書(shū)抄一遍假裝會(huì)了。4.4 坑四英文原版的長(zhǎng)句和術(shù)語(yǔ)把閱讀速度拖成龜速現(xiàn)象非母語(yǔ)讀者直接讀英文原版每段都要停下來(lái)查單詞一段三百字的內(nèi)容要讀十分鐘很難堅(jiān)持到第 4 章。越讀越慢越慢越挫敗最后只能放棄。原因教材的英文是學(xué)術(shù)性敘述大量長(zhǎng)從句、被動(dòng)語(yǔ)態(tài)和術(shù)語(yǔ)堆疊。問(wèn)題不是英語(yǔ)語(yǔ)法沒(méi)過(guò)關(guān)而是“查閱功耗”太高大部分精力被消耗在語(yǔ)言上而不是算法邏輯上。解決改用目標(biāo)驅(qū)動(dòng)的局部閱讀法不逐句翻譯只看四個(gè)點(diǎn)位算法輸入輸出、核心步驟描述、復(fù)雜度結(jié)論、證明的關(guān)鍵斷言。術(shù)語(yǔ)方面自己建一張中英對(duì)照術(shù)語(yǔ)表每章只記十到十五個(gè)核心詞就好。如果長(zhǎng)時(shí)間閱讀速度上不來(lái)可以前五章和附錄部分配合中文譯本一起讀后面章節(jié)再回到英文原版。后期代碼和公式的占比很高語(yǔ)言障礙對(duì)理解的影響會(huì)明顯降低。讀英文版的目的不是學(xué)英語(yǔ)是抓住算法的骨架別讓語(yǔ)言成為你與好內(nèi)容之間的墻。5. 把算法導(dǎo)論當(dāng)代碼庫(kù)用從偽代碼到可運(yùn)行實(shí)現(xiàn)的翻譯技巧5.1 偽代碼約定速查縮進(jìn)、索引與返回值翻譯偽代碼之前先把它的五條約定記清楚?？s進(jìn)表示塊結(jié)構(gòu)同一縮進(jìn)級(jí)別是同一個(gè)循環(huán)體或分支體翻譯成 Python 時(shí)注意嵌套層級(jí)不要散掉。數(shù)組索引從 1 開(kāi)始所有下標(biāo)運(yùn)算都要做整體平移。變量默認(rèn)是過(guò)程局部變量遞歸調(diào)用時(shí)每次調(diào)用重新綁定不要誤寫(xiě)成共享的全局狀態(tài)。數(shù)組參數(shù)按引用傳遞過(guò)程內(nèi)修改數(shù)組會(huì)影響調(diào)用方這一點(diǎn)和 Python 列表的行為正好吻合。最后一條容易被忽略A.length和A.heap-size是兩個(gè)不同的屬性前者是數(shù)組容量后者是堆的有效長(zhǎng)度在堆排序里前者不變后者遞減。下面這張表是翻譯時(shí)最常見(jiàn)的對(duì)應(yīng)關(guān)系偽代碼表達(dá)含義Python 等價(jià)寫(xiě)法A[1..n]長(zhǎng)度為 n 的數(shù)組0 基列表或 a [0] arrfor j p to r閉區(qū)間循環(huán)for j in range(p, r1)exchange A[i] with A[j]交換兩個(gè)位置a[i], a[j] a[j], a[i]return x返回值return xA.heap-size堆的有效長(zhǎng)度heap_size 獨(dú)立變量哨兵 ∞無(wú)窮占位float(inf)注意偽代碼中A.heap-size的合法下標(biāo)是 1 到 A.heap-size在 0 基語(yǔ)言中有效下標(biāo)變成 0 到 heap_size-1。這是堆排序翻譯中最容易出問(wèn)題的位置我見(jiàn)過(guò)不止一個(gè)人在這里翻車(chē)最后排查半天發(fā)現(xiàn)只是下標(biāo)差了一位。5.2 三個(gè)可直接照抄的經(jīng)典實(shí)現(xiàn)二分查找、堆排序、快速排序以下三個(gè)實(shí)現(xiàn)覆蓋了遍歷查找、完全二叉樹(shù)原地排序、遞歸分治三類(lèi)典型結(jié)構(gòu)分別對(duì)應(yīng)第 2 章練習(xí)、第 6 章和第 7 章的核心算法。代碼可以直接復(fù)用到自己的練習(xí)項(xiàng)目里。def binary_search(a, target): 在升序列表中查找 target返回下標(biāo)找不到返回 -1 left, right 0, len(a) - 1 while left right: mid (left right) // 2 if a[mid] target: return mid elif a[mid] target: left mid 1 # 目標(biāo)在右半?yún)^(qū) else: right mid - 1 # 目標(biāo)在左半?yún)^(qū) return -1邏輯說(shuō)明每次循環(huán)把搜索范圍縮小一半循環(huán)條件left right保證空區(qū)間時(shí)正常退出。mid 取左中位當(dāng)a[mid] target時(shí)目標(biāo)只可能在 mid 右側(cè)所以left mid 1而不是mid這是避免死循環(huán)的關(guān)鍵。時(shí)間復(fù)雜度 O(log n)空間復(fù)雜度 O(1)。參數(shù)說(shuō)明a 必須是升序數(shù)組否則結(jié)果無(wú)意義target 可以是任何可比較類(lèi)型。在 Python 中(left right) // 2不會(huì)溢出但在 C 或 Java 里兩個(gè)大整數(shù)相加可能溢出更穩(wěn)的寫(xiě)法是left (right - left) // 2面試時(shí)可以主動(dòng)提這一點(diǎn)。def max_heapify(a, heap_size, i): 維護(hù)以 i 為根的子樹(shù)滿足最大堆性質(zhì) left 2 * i 1 # 0 基下左孩子下標(biāo) right 2 * i 2 # 0 基下右孩子下標(biāo) largest i if left heap_size and a[left] a[largest]: largest left if right heap_size and a[right] a[largest]: largest right if largest ! i: a[i], a[largest] a[largest], a[i] max_heapify(a, heap_size, largest) def heapsort(a): n len(a) # 建堆從最后一個(gè)非葉節(jié)點(diǎn)開(kāi)始向上調(diào)整 for i in range(n // 2 - 1, -1, -1): max_heapify(a, n, i) # 依次把堆頂換到末尾再對(duì)縮小的堆重新調(diào)整 for i in range(n - 1, 0, -1): a[0], a[i] a[i], a[0] max_heapify(a, i, 0)邏輯說(shuō)明max_heapify 假設(shè) i 的左右子樹(shù)已經(jīng)是合法最大堆只負(fù)責(zé)把 i 下沉到正確位置。建堆從n // 2 - 1開(kāi)始因?yàn)檫@是最后一個(gè)非葉節(jié)點(diǎn)在 0 基數(shù)組中的下標(biāo)從它倒序遍歷到 0保證每個(gè)子樹(shù)先滿足堆性質(zhì)再處理上層。排序階段每輪把堆頂最大值交換到數(shù)組末尾然后對(duì)去掉末尾的新堆重新調(diào)整max_heapify(a, i, 0)里的 i 是新的堆大小不是下標(biāo)上界。整個(gè)過(guò)程原地完成空間復(fù)雜度 O(1)。參數(shù)說(shuō)明heapsort 原地修改列表要求 a 支持下標(biāo)訪問(wèn)和元素交換。時(shí)間復(fù)雜度穩(wěn)定在 O(n log n)但它是不穩(wěn)定排序如果需要穩(wěn)定排序要用歸并。翻譯時(shí)最容易錯(cuò)的就是下標(biāo)換算偽代碼里left 2*i在 0 基下必須改成2*i1這一步錯(cuò)了整個(gè)堆結(jié)構(gòu)就塌了。def partition(a, lo, hi): 以 a[hi] 為基準(zhǔn)把不大于基準(zhǔn)的元素放到左側(cè)返回基準(zhǔn)最終下標(biāo) pivot a[hi] i lo - 1 # i 是已劃分區(qū)間的右邊界 for j in range(lo, hi): if a[j] pivot: i 1 a[i], a[j] a[j], a[i] a[i 1], a[hi] a[hi], a[i 1] return i 1 def quicksort(a, lo, hi): if lo hi: p partition(a, lo, hi) quicksort(a, lo, p - 1) # 遞歸處理基準(zhǔn)左側(cè) quicksort(a, p 1, hi) # 遞歸處理基準(zhǔn)右側(cè)邏輯說(shuō)明partition 維護(hù)兩個(gè)區(qū)間[lo, i] 是已確定不大于 pivot 的部分[i1, j-1] 是等待處理的部分。掃描過(guò)程中每次遇到不大于 pivot 的值就把它交換到已劃分區(qū)間的尾部。掃描結(jié)束后把 pivot 從 hi 交換到 i1此時(shí) pivot 已經(jīng)處在最終正確位置所以遞歸區(qū)間必須排除 p 本身否則會(huì)無(wú)限遞歸。參數(shù)說(shuō)明lo、hi 是閉區(qū)間端點(diǎn)首次調(diào)用quicksort(a, 0, len(a)-1)?；鶞?zhǔn)取a[hi]實(shí)現(xiàn)簡(jiǎn)單但最壞情況下已排序數(shù)組會(huì)讓復(fù)雜度退化成 O(n2)第 7.3 節(jié)專門(mén)講了隨機(jī)化改進(jìn)方案實(shí)際工程中更常用三數(shù)取中。Lomuto 劃分比 Hoare 劃分容易寫(xiě)對(duì)代價(jià)是交換次數(shù)略多面試時(shí)用 Lomuto 版本基本夠用。如果繼續(xù)翻譯第 8 章的計(jì)數(shù)排序、基數(shù)排序、桶排序可以沿用同一套思路先把數(shù)組索引改成 0 基再單獨(dú)處理穩(wěn)定性。計(jì)數(shù)排序的累加數(shù)組和輸出位置關(guān)系是最大坑點(diǎn)寫(xiě)錯(cuò)一次輸出順序就全亂了建議翻譯完立刻用第 5.3 節(jié)的對(duì)拍腳本驗(yàn)證。5.3 對(duì)拍測(cè)試用隨機(jī)數(shù)據(jù)驗(yàn)證翻譯是否正確翻譯完不測(cè)試等于白寫(xiě)。我自己的習(xí)慣是寫(xiě)完一個(gè)算法馬上用語(yǔ)言內(nèi)置的排序函數(shù)做對(duì)拍隨機(jī)生成大量數(shù)據(jù)把被測(cè)函數(shù)的結(jié)果和內(nèi)置結(jié)果逐一對(duì)比。下面這個(gè)腳本可以直接復(fù)用import random def check_sort(sort_fn, rounds200, size1000): 用內(nèi)置 sorted 做基準(zhǔn)隨機(jī)測(cè)試 sort_fn 的原地排序結(jié)果 for _ in range(rounds): arr [random.randint(-10000, 10000) for _ in range(size)] expected sorted(arr) sort_fn(arr) if arr ! expected: print(排序結(jié)果不一致) print(樣例:, arr[:20], expected[:20]) return False print(f{rounds} 輪隨機(jī)測(cè)試全部通過(guò)) return True if __name__ __main__: check_sort(heapsort)邏輯說(shuō)明每輪生成隨機(jī)整數(shù)列表先用內(nèi)置 sorted 得到期望結(jié)果再調(diào)用被測(cè)排序函數(shù)原地修改數(shù)組最后逐元素比較。隨機(jī)數(shù)據(jù)里包含正負(fù)數(shù)、重復(fù)值能覆蓋絕大多數(shù)邊界情況。如果想專門(mén)測(cè)空數(shù)組和單元素?cái)?shù)組可以額外手寫(xiě)兩個(gè)固定用例調(diào)用排序函數(shù)檢查。參數(shù)說(shuō)明rounds 控制測(cè)試輪數(shù)size 控制數(shù)組長(zhǎng)度。對(duì) O(n log n) 的排序來(lái)說(shuō)1000 元素跑 200 輪在毫秒級(jí)完成完全不用擔(dān)心性能。這個(gè)腳本可以替換成任何排序函數(shù)堆排、快排、插入排序都能用也可以改造成驗(yàn)證二分查找生成升序數(shù)組后隨機(jī)取一個(gè)存在的和不存在的值分別檢查返回值是否正確。對(duì)拍通過(guò)后我還會(huì)做一次“可視化小樣”檢查把數(shù)組長(zhǎng)度改成 2、3、4 各跑一遍打印每輪排序后的數(shù)組人眼確認(rèn)執(zhí)行軌跡和第 4 章、第 6 章、第 7 章的圖例一致。這一步不是驗(yàn)證正確性而是確認(rèn)自己真的理解算法每一步在做什么。只有機(jī)器驗(yàn)證通過(guò)、人眼也看懂了翻譯才算真正完成。6. 高階驗(yàn)證與延伸用一晚上親手驗(yàn)證排序算法的增長(zhǎng)曲線6.1 最小實(shí)驗(yàn)設(shè)計(jì)隨機(jī)數(shù)據(jù)測(cè)出兩種排序的耗時(shí)曲線讀完前九章你會(huì)得到一組復(fù)雜度結(jié)論插入排序 O(n2)快速排序 O(n log n)。結(jié)論背起來(lái)容易但如果你沒(méi)親眼見(jiàn)過(guò)這兩種增長(zhǎng)曲線的差異遇到復(fù)雜度分析還是容易發(fā)虛。一個(gè)成本極低、收益很高的實(shí)驗(yàn)是固定隨機(jī)數(shù)據(jù)分布把 n 從 500 翻倍到 16000分別測(cè)插入排序和快速排序的耗時(shí)觀察 n 翻倍時(shí)耗時(shí)的增長(zhǎng)倍數(shù)。import random import time def timed_run(sort_fn, arr): buf arr[:] # 復(fù)制數(shù)據(jù)避免原地排序污染后續(xù)測(cè)量 t0 time.perf_counter() sort_fn(buf) return time.perf_counter() - t0 for n in (500, 1000, 2000, 4000, 8000, 16000): data [random.randint(0, 10**6) for _ in range(n)] t1 timed_run(insertion_sort, data) t2 timed_run(quicksort, data, 0, len(data) - 1) print(fn{n:6d} insertion{t1*1000:8.2f}ms quick{t2*1000:8.2f}ms)邏輯說(shuō)明timed_run 先把數(shù)組復(fù)制一份再計(jì)時(shí)確保每次測(cè)量都在相同的數(shù)據(jù)分布上進(jìn)行。插入排序?qū)崿F(xiàn)用第 3.2 節(jié)的版本快速排序用第 5.2 節(jié)的版本。perf_counter 是 Python 里精度最高的計(jì)時(shí)接口適合這種毫秒級(jí)的測(cè)量。參數(shù)說(shuō)明n 從 500 翻倍到 16000插入排序在隨機(jī)數(shù)據(jù)下到 16000 時(shí)大概耗時(shí)幾十到幾百毫秒快速排序則在幾毫秒到幾十毫秒?yún)^(qū)間。如果數(shù)據(jù)已經(jīng)有序快速排序會(huì)退化到 O(n2)測(cè)出來(lái)的曲線會(huì)異常陡峭這時(shí)要先用 random.shuffle 打亂數(shù)據(jù)再測(cè)。6.2 用數(shù)據(jù)反向驗(yàn)證理論復(fù)雜度把實(shí)驗(yàn)跑完你會(huì)看到一組非常有說(shuō)服力的比值n 從 1000 翻到 2000插入排序的耗時(shí)大約翻 4 倍因?yàn)?(2n)2 / n2 4快速排序的耗時(shí)大約翻 2.1 到 2.4 倍因?yàn)?n log n 的增長(zhǎng)比線性略快但遠(yuǎn)慢于平方。這個(gè)觀察直接把第 3 章漸近記號(hào)的抽象定義變成了眼前的事實(shí)。如果測(cè)出來(lái)的倍數(shù)遠(yuǎn)小于理論預(yù)期先檢查兩種邊界情況一是數(shù)據(jù)是否被排序過(guò)有序輸入會(huì)讓插入排序退化成 O(n)也會(huì)讓固定基準(zhǔn)的快速排序惡化二是測(cè)試規(guī)模太小計(jì)時(shí)器的噪聲蓋過(guò)了真實(shí)的耗時(shí)差異。把 n 的上限提高到 50000 再跑一輪曲線差異會(huì)清晰得多。這套方法論不只適用于排序紅黑樹(shù)插入、Dijkstra 堆優(yōu)化、KMP 匹配都能用同樣的方式來(lái)驗(yàn)證。從那以后我每次讀完一個(gè)復(fù)雜度的結(jié)論都會(huì)順手跑一個(gè)最小實(shí)驗(yàn)驗(yàn)證它的增長(zhǎng)曲線而不是直接背結(jié)論。這個(gè)習(xí)慣幫我避開(kāi)了很多“看上去合理”的錯(cuò)誤記憶也讓書(shū)里的公式不再是黑匣子。這份算法導(dǎo)論第四版 PDF 值得放進(jìn)你的算法工具庫(kù)但要真正起作用還是要靠你親手把偽代碼跑起來(lái)。希望幫到你。本文還有配套的精品資源點(diǎn)擊獲取