演算法導論

引用

Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2022). Introduction to Algorithms (4th ed.). The MIT Press.

章節概要

第四版共有 35 章，分為七個部分，之後是數學背景附錄，全書約 1,300 頁。每一部分都以一篇簡短的導言開頭。

第一部分，第1–5章：基礎

第1章“演算法在計算中的角色”（The Role of Algorithms in Computing）和第2章“入門”（Getting Started）介紹演算法及其分析。第3章“刻畫執行時間”（Characterizing Running Times）講漸近記號；第4章“分治”（Divide-and-Conquer）是這一部分中篇幅最長的章節之一；第5章“機率分析與隨機演算法”（Probabilistic Analysis and Randomized Algorithms）為後文的隨機化方法打下基礎。

第二部分，第6–9章：排序與順序統計量

堆排序、快速排序、線性時間排序，以及中位數與順序統計量。這幾章合起來涵蓋比較排序、非比較排序和選擇問題。

第三部分，第10–13章：資料結構

基本資料結構、散列表、二叉搜尋樹和紅黑樹。散列表有一章約四十頁的篇幅，本版的更新說明中也列出了散列表的新增內容。

第四部分，第14–16章：高階設計與分析技術

動態規劃、貪心演算法和攤還分析。動態規劃是全書較長的章節之一（約55頁）。這一部分介紹了兩種主要的最佳化問題設計策略，以及分析操作序列的主要工具。

第五部分，第17–19章：高階資料結構

資料結構的擴張、B 樹和不相交集合的資料結構。

第六部分，第20–25章：圖演算法

基本圖演算法、最小生成樹、單源最短路徑、所有結點對最短路徑、最大流，以及二分圖中的匹配。最後一章是本版新增的。

第七部分，第26–35章：專題選講

並行演算法、線上演算法、矩陣運算、線性規劃、多項式與快速傅立葉變換、數論演算法、字串匹配、機器學習演算法、NP 完全性和近似演算法。線上演算法和機器學習演算法是本版新增的章節。NP 完全性和近似演算法為這一部分收尾。

附錄：數學背景

求和、集合等、計數與機率、矩陣（附錄 A–D），之後是參考文獻和索引。

核心概念

第1–5章

• 漸近記號與執行時間：不依賴具體機器、用來比較演算法的一套詞彙，在第3章展開。
• 分治與遞迴式：第4章把遞迴式設計與求解由此產生的遞迴方程的方法放在一起講。
• 隨機演算法：第5章引入對演算法的機率分析。

第6–19章

• 排序下界與選擇：第6–9章區分比較排序與線性時間排序，並講授順序統計量。
• 動態規劃、貪心演算法、攤還分析：第四部分的三種技術。
• 平衡與擴張的搜尋結構：紅黑樹、B 樹及資料結構的擴張（第13、17、18章）。

第20–35章

• 最短路徑、生成樹、流與匹配：第六部分的圖演算法各章。
• NP 完全性與近似：第34、35章，討論被認為沒有高效精確演算法的問題及其近似。
• 專題選講：並行與線上演算法、線性規劃、快速傅立葉變換、數論、字串匹配和機器學習，各為簡短而自足的一章。

評析

優點

• 嚴謹而全面。 出版社稱本書兼具嚴謹性與全面性，各章自成體系，演算法用虛擬碼書寫，讀者可以從許多地方切入。
• 附有數學背景。 附錄 A–D 涵蓋求和、集合、計數與機率、矩陣，大部分預備知識可以在書中自行復習。
• 習題與思考題。 第四版新增 140 道習題和 22 道思考題，並根據讀者反饋改進了原有的題目。
• 內容較新。 本版新增了二分圖匹配、線上演算法和機器學習三章，並在遞迴式、散列表、勢函式和字尾陣列方面增加了新內容。

侷限

• 篇幅龐大。 全書 35 章、一千多頁，既是教材也是參考書；沒有哪一門課程能覆蓋全部內容，讀者必須取捨。
• 只有虛擬碼。 演算法以虛擬碼給出，想要可執行程式的讀者需要自行實現。
• 專題部分較簡略。 線性規劃（約27頁）和機器學習（約39頁）等主題各只有一章，更像入門介紹，而不是完整論述。
• 對初學者要求較高。 數學化的寫法和篇幅使它作為演算法的第一本書比較吃力；配合課堂講授或作為第二遍閱讀效果更好。

在課程中的定位

在演算法課程中，這是一本綜合性的參考書。Cormen 自己的 Algorithms Unlocked 是一本講解演算法如何工作的簡短入門書，寫給尚未準備好讀本書的讀者；Roughgarden 的 Algorithms Illuminated 用對話式的風格講解標準的設計範式，並配有影片講座。兩者都適合作為第一遍閱讀。Skiena 的 The Algorithm Design Manual 是識別問題、選擇設計方案的實用指南，並附有問題目錄，當目標是實現時，與本書搭配很合適。

在專門方向上，本書第35章是對近似演算法的簡短介紹，Vazirani 的 Approximation Algorithms 與 Williamson 和 Shmoys 的 The Design of Approximation Algorithms 則作了完整展開。Mitzenmacher 等人的 Probability and Computing 擴充套件了第5章開始的隨機化內容。

如何使用本書

本書適合高年級本科生和研究生，也可以作為長期的參考書。熟悉證明、求和與基本機率會有幫助，附錄 A–D 可以用來復習。

典型的第一門課程讀第一、二部分，再選讀第三、四部分的若干章節（散列表、二叉搜尋樹、動態規劃、貪心演算法），然後讀第六部分的基本圖演算法、生成樹和最短路徑。攤還分析、B 樹、最大流和 NP 完全性是自然的第二學期主題。第七部分各章大多相互獨立，可按興趣任意順序閱讀。

閱讀每一章時請配合習題和思考題。虛擬碼最好先用手逐步跟蹤，再用自己選擇的語言寫出來。