算法导论（原书第3版）

返回分类书单

分类：计算机与软件工程 / 数据结构、算法与软件设计

书籍简介

Thomas H. Cormen、Charles E. Leiserson、Ronald L. Rivest 与 Clifford Stein 合著的《算法导论》，通常以作者姓氏首字母简称 CLRS。它将算法的描述、正确性证明和复杂度分析结合起来，适合希望系统学习算法设计的读者。

这不是必须一次顺读完的书。可以先学习基础分析、排序、基本数据结构、动态规划和图算法，再按问题需要进入高级结构、数论或复杂性理论。每次阅读都应尝试回答：算法为什么正确，成本依赖哪些假设。

版本说明

本页对应 2009 年出版的英文第三版，整理其 35 章主体与数学附录；不混入第四版新增或调整后的章节。中文章名为便于阅读的转述，页码与译名以具体中文印次为准。作者主页用于核对版本，章节排列另与第三版公开学习索引交叉核对。

作者与背景

本书由四位作者合著，通常简称 CLRS。MIT Press 的作者介绍列出他们的学术背景：

作者	背景与本书的可信依据
Thomas H. Cormen	达特茅斯学院计算机科学荣休教授，1992 年获 MIT 博士学位；参与算法教学，并维护教材版本说明与勘误。
Charles E. Leiserson	MIT 电气工程与计算机科学教授，将算法教学与研究经验带入教材。
Ronald L. Rivest	MIT Institute Professor，参与本书算法体系的共同编写。
Clifford Stein	哥伦比亚大学工业工程与运筹学、计算机科学教授，专业背景连接离散算法与优化问题。

长期教学研究、可检查的证明和公开勘误是本书可信度的重要依据。阅读时仍应按第三版印次核对错误，并亲自检查推导中的假设。

目标读者

适合具备基础编程、离散数学和概率知识，希望系统学习算法设计的本科生、自学者及开发者。求职备考可选读基础、动态规划与图算法；数学基础薄弱者可以先补附录，不宜把全书一次通读作为入门门槛。

章节介绍

章节	核心内容
第1章 算法在计算中的作用	说明算法作为技术的意义，以及正确性、效率与资源约束的关系。
第2章 算法基础	通过插入排序和归并排序学习描述、分析与设计算法。
第3章 函数的增长	建立渐近记号与增长率比较，区分上界、下界和紧确界。
第4章 分治策略	用递归分解问题，并通过代入、递归树和主方法分析递推式。
第5章 概率分析和随机算法	使用随机变量与期望分析行为，区分随机输入假设和算法主动随机化。
第6章 堆排序	介绍二叉堆、维护堆性质和优先队列。
第7章 快速排序	分析划分、随机化与递归代价，理解平均表现和最坏情况的差别。
第8章 线性时间排序	比较计数、基数和桶排序，解释它们依赖的输入假设。
第9章 中位数和顺序统计量	学习选择第 k 小元素，比较期望线性与最坏线性时间方案。
第10章 基本数据结构	介绍栈、队列、链表和树的表示，连接抽象操作与具体实现。
第11章 散列表	讨论散列函数、冲突处理、开放寻址与完全散列。
第12章 二叉搜索树	分析查找、插入和删除，以及树形状对效率的影响。
第13章 红黑树	通过颜色约束和旋转保持平衡，理解局部调整维护全局性质。
第14章 数据结构的扩张	在已有结构上维护额外信息，以支持顺序统计和区间查询。
第15章 动态规划	使用最优子结构与重复子问题，组织状态、转移和答案恢复。
第16章 贪心算法	分析局部选择成立的条件，并通过活动选择和编码等问题建立证明。
第17章 摊还分析	用聚合、记账和势能方法分析一串操作的总成本。
第18章 B 树	面向外部存储组织多路搜索树，关注节点访问与磁盘代价。
第19章 斐波那契堆	介绍可合并堆及其摊还效率，理解延迟维护的设计思想。
第20章 van Emde Boas 树	利用整数值域递归分解，讨论特殊键空间下的查找结构。
第21章 不相交集合的数据结构	介绍并查集、按秩合并与路径压缩。
第22章 基本的图算法	讲解图表示、广度与深度优先搜索、拓扑排序和强连通分量。
第23章 最小生成树	用安全边与切割性质解释 Kruskal 和 Prim 算法。
第24章 单源最短路径	比较 Bellman–Ford、Dijkstra 和有向无环图算法，注意边权前提。
第25章 所有结点对的最短路径	介绍矩阵思路、Floyd–Warshall 和 Johnson 算法。
第26章 最大流	使用残量网络与增广路径，并讨论推送重贴标签和二分图匹配。
第27章 多线程算法	用工作量与关键路径分析并行计算，认识并行度的理论限制。
第28章 矩阵运算	讨论线性方程组、求逆与最小二乘等计算问题。
第29章 线性规划	将约束优化写成标准形式，介绍单纯形、对偶与可行解。
第30章 多项式与快速傅里叶变换	比较多项式表示，利用 FFT 加速相关运算。
第31章 数论算法	包括最大公约数、模运算、素性测试及 RSA 所需的算法背景。
第32章 字符串匹配	比较朴素匹配、Rabin–Karp、有限自动机和 KMP。
第33章 计算几何学	讨论线段相交、凸包与最近点对，关注几何性质如何支持算法。
第34章 NP 完全性	理解多项式验证、归约与 NP 完全性证明，区分求解和验证。
第35章 近似算法	在难解问题中分析近似比，研究覆盖、旅行商等问题的可行策略。

数学附录分别补充求和、集合与关系、计数与概率、矩阵。这些内容适合在证明或分析遇到困难时回查，不必全部读完后才开始算法部分。

读后感

以下为本站阅读评析，用可实践的阅读目标表达收获，不代表书单提供者已经读完、任职或完成相应项目。版本未明时，评析只针对本页明确标注的主题或参考版本。

金句摘抄或阅读提炼

样例展示结果，不变量解释结果为何成立。

这是本站原创阅读提炼，不是原书引文；没有可核对页码的原文不作逐字摘抄。

个人收获

读一个算法时留下三件成果：输入前提、正确性论证、成本推导。例如比较 Dijkstra 与 Bellman–Ford 时，除了运行时间，还要明确边权条件；这比只按复杂度挑“更快算法”更可靠。

客观评价与阅读建议

体系广、证明完整，但篇幅和练习量对初学者构成负担，伪代码也不能直接替代可运行实现。建议选一条主线，先实现再对照证明，第三版没有覆盖的后续发展另查资料。

推荐语（本站原创，非原书引用）： 推荐给愿意追问“为什么”的读者：即使只认真完成排序、动态规划与图算法三条线，也能建立长久的分析习惯。

来源与核对入口

• Thomas H. Cormen 作者主页：核对第三版出版年份、版次区别与勘误入口。
• MIT Press 第三版书目与作者介绍：核对四位作者的学术背景与英文版出版信息。
• CLRS 第三版公开学习索引：35 章结构的交叉核对来源；这是社区学习资料，并非出版社答案手册。
• 第三版勘误入口：阅读时可按印次检查已知错误。