演算法導論

引用

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

章節概要

第四版共有 35 章，分為七個部分，之後是數學背景附錄，全書約 1,300 頁（MIT Press 標示 2022 年出版的精裝本為 1,312 頁）。每一部分都以一篇簡短的導言開頭。

第一部分，第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章把遞迴式設計與求解由此產生的遞迴方程的方法放在一起講。MIT Press 將遞迴方程的新增內容列為第四版的更新之一。
• 隨機演算法：第5章引入對演算法的機率分析。

第6–19章

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

第20–35章

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

評析

優點

• 嚴謹而全面。 出版社稱本書兼具嚴謹性與全面性，各章自成體系，演算法用虛擬碼書寫，讀者可以從許多地方切入。
• 附有數學背景。 附錄 A–D 涵蓋求和、集合、計數與機率、矩陣，大部分預備知識可以在書中自行復習。
• 習題與思考題。 第四版新增 140 道習題和 22 道思考題，並根據讀者反饋改進了原有的題目。
• 內容較新。 本版新增了二分圖匹配、線上演算法和機器學習三章，並在遞迴式、散列表、勢函式和字尾陣列方面增加了新內容。
• 改進的呈現方式。 據 MIT Press 介紹，第四版加入了彩色印刷，並修訂文字，使其更清晰、更具個人色彩且使用性別中立的表述。
• 長期的教學記錄。 數十年來各地課程持續指定本書，而且通常只選讀部分章節，以模組化方式使用。下文「常見課程指定閱讀」列出了近期的例子和較早的存檔清單。請留意版本：第二版出版於 2001 年，第三版於 2009 年，第四版於 2022 年。

侷限

• 篇幅龐大。 全書 35 章、一千多頁，既是教材也是參考書；沒有哪一門課程能覆蓋全部內容，讀者必須取捨。下文所列的課程沒有一門指定全書，例如史丹佛 2016 年的課程只指定個別小節，而不是整個部分。
• 只有虛擬碼。 演算法以虛擬碼給出，想要可執行程式的讀者需要自行實現。
• 專題部分較簡略。 線性規劃（約27頁）和機器學習（約39頁）等主題各只有一章，更像入門介紹，而不是完整論述。
• 對初學者要求較高。 數學化的寫法和篇幅使它作為演算法的第一本書比較吃力；配合課堂講授或作為第二遍閱讀效果更好。
• 課程材料的版本不一致。 多份可免費取得的課綱對應的是舊版（第三版甚至第二版）。第四版重新編排了部分章節編號（尤其是圖演算法部分），並增加了新章節，因此舊的閱讀清單無法直接套用。

在課程中的定位

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

Kleinberg 與 Tardos 的 Algorithm Design 在下文史丹佛 2016 年的課程中被列為替代教材。

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

如何使用本書

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

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

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

常見課程指定閱讀

已公布的閱讀清單顯示了各課程如何有選擇地使用本書。章節編號依照各課綱所標明的版本——並非全都對應第四版。第四版重新編排了大部分圖演算法內容的編號（例如基本圖演算法在第四版課綱中為第20章，在第三版課綱中則為第22章），並增加了新章節，因此在照搬舊清單之前，請先用 MIT Press 的第三版至第四版過渡指南對照主題。

近期（約八年內）：

• 約翰霍普金斯大學 601.433/633，2024 年秋季（指定第三版；第四版亦可）： 課表閱讀涵蓋第1–9、11–13、15–18、21–26、29 和 34–35 章，後段講次另有線上演算法與演算法學習。這是一門大學部／研究所的全面課程，從漸近分析與排序一路講到圖、流、線性規劃、NP 完全性和近似。（課表）
• MIT OCW 6.006，2020 年春季（第三版為選讀參考）： 書面材料為講課與習題課講義；CLRS 第三版被列為有用但非必需的參考書。（課綱）

第四版課綱（頁面未註明學年）：

• 科羅拉多大學丹佛分校 CSCI 5451（第四版，2022 年教材）： 第1、3–4、6–7、9、12–15、19–24、28–29、32、34–35 章。明確採用第四版編號（基本圖演算法為第20章、最小生成樹為第21章、最大流為第24章）。（課程頁面）

較早的存檔清單：

• 史丹佛 CS 161，2016 年春季（第三版）： 第1章；2.3、3.1；4.3–4.5；第9章；第7與第5章；8.1–8.2；第12章；第11章；第22章；第24與第6章；24.3；24.1 與 24.3；25.2 與 15.4；第16與第23章；26.1–26.3。
• MIT OCW 6.006，2011 年秋季（第三版）： 第1與第3章；2.1–2.3、4.3–4.6；6.1–6.4；12.1–12.3；8.1–8.3；11.1–11.4；17；22.1–22.4；24.；15.；34.1–34.3。
• MIT OCW 6.046J，2005 年秋季（第二版，2001）： 第1–9、11–17、22–25 章。早於 2009 年的第三版；章節編號應視為第二版編號。
• 加州大學柏克萊分校 CS 170，2005 年秋季（第二版）： 第1–5、11、15、16.3、21–24、26、29–30、34–35 章。同樣注意：是第二版，不是第三版。

綜觀這些清單，基礎、排序、雜湊、基本圖演算法和動態規劃構成共同核心；後段的「專題選講」章節只出現在部分課程中。

版本說明

MIT Press 2022 年第四版精裝本的 ISBN 為 9780262046305（電子版使用其他識別碼）。在依照任何課綱閱讀之前，請先核對手上版本的節名和虛擬碼。將第三版的閱讀對應到第四版章節編號時，請使用上述過渡指南，而不要僅憑標題猜測。