《算法导论》：从“能运行”到“能证明、能比较”

系统学习算法设计、正确性证明和复杂度分析，而非背诵题型。

笔记状态：结构化初读｜作者：Thomas H. Cormen、Charles E. Leiserson、Ronald L. Rivest、Clifford Stein

版本与阅读范围

本地文件标注第三版，但 PDF 仅 67 个大幅扫描页，需警惕合并、版面或完整性问题。报告依据第三版目录与 MIT Press 第四版官方说明整理；这本书应作为体系教材和参考书，不建议一次线性通读。

一句话结论

算法学习的核心是把问题、正确性、资源成本和适用条件说清楚，而不是背下一段伪代码。

核心论点一：正确性必须由不变量和结构证明

循环不变量、数学归纳和交换论证等方法把“几个样例跑通”提升为“对所有满足前提的输入成立”。算法的前置条件、结束性和结果性质共同构成证明责任。

书的论据不是经验意见，而是定义、定理、证明和反例。它的强项是可检验性；弱点是读者可能照抄证明形式，却没有识别现实输入是否满足模型假设。

核心论点二：渐近分析建立跨机器的增长率语言

O、Ω、Θ 忽略常数和低阶项，比较输入规模增长时资源需求。递归式、均摊分析和概率分析把不同算法放到统一尺度。

论证链是：定义输入规模与基本操作 → 建立成本函数 → 取增长阶 → 比较可扩展性。它适合排除增长率错误的方案，却不能取代基准测试；缓存、并行、常数、数据分布和实现质量会决定实际交叉点。

核心论点三：设计范式比单个算法更可迁移

分治、动态规划、贪心、随机化、图算法和线性规划代表不同的问题分解方式。真正能力是识别子问题结构、最优子结构和约束，而不是记住排序代码。

每种范式都通过“问题定义 → 算法 → 正确性 → 复杂度 → 练习”论证。练习不是附属物，而是检验是否能迁移方法的主要证据。

当代对照与不同观点

• MIT Press 第四版在 2022 年加入二分图匹配、在线算法和机器学习等内容，并更新哈希、势函数和后缀数组；本地第三版仍可学基础，但不是最新内容索引。第四版官方页面
• 理论上最优不等于生产中最快。真实工程需要用代表性工作负载、内存层次和库实现做测量；反过来，单次 benchmark 也不能证明规模增长后的行为。
• 不是每个业务问题都值得追求最优算法。数据量、实现风险和维护成本较小时，简单且显然正确的方案可能更优。

推荐读法

• 主线：渐近分析、分治、排序、哈希、树、动态规划、贪心、图。
• 每章至少完成一个正确性证明和一个可运行实现。
• 建立“四栏算法卡”：前提、不变量、复杂度、失败边界。

最终评价

它不是面试题词典，而是一套关于计算资源的严格语言。只读正文会高估掌握程度；证明、练习和实验才完成论证闭环。