简介《算法导论》第四版英文PDF是计算机算法领域的权威教材由Cormen、Leiserson、Rivest与Stein四位学者合著2022年经麻省理工学院出版社发行面向计算机专业学生、算法学习者及软件开发与研究人员用于系统建立算法设计与分析的理论基础。资源包共1个文件为21.14MB的PDF非扫描版排版清晰、文字可检索便于阅读与摘录。内容从算法在计算中的角色切入以插入排序为例讲解算法实现与分析进而引入O、Ω、Θ等渐近记号刻画运行时间分治部分涵盖矩阵乘法与Strassen算法、代换法、递归树法与主方法求解递归式并延伸至堆排序、快速排序、线性时间排序、动态规划、图算法、字符串处理与计算几何等主题配有实例、步骤解析与参考文献索引。目前已有1413人学习适合作为课程配套读物与案头工具书反复查阅。1. 算法学习的地图从《算法导论》第四版看整条知识主线很多人把《算法导论》当成一本“字典”遇到哪个算法不会就去翻哪一章结果翻完还是不会分析复杂度更不会在题目里认出该用哪种设计策略。真正系统学过一遍的人会发现这本书的组织方式本身就是一张知识地图先打基础伪代码、渐进记号、递归式求解再按“排序与顺序统计—数据结构—高级设计与分析—高级数据结构—图算法—专题”逐层加码。第四版在 2022 年更新后新增了并行算法、在线算法、机器学习算法等章节把传统算法课和现代工程场景接上了。这份笔记面向正在系统学算法、或者备考数据结构与算法科目的人把全书拆成可复习的模块标出重点难点和容易翻车的地方让你拿着就能对照查漏补缺。2. 基础层渐进记号与递归式全书的地基第一部分 Foundations 看起来只是热身实际上决定了后面每一章你能不能读懂分析过程。插入排序本身不难难的是从它身上学会“最坏情况分析”和“增长量级”的思维方式分治法的三个求解递归式方法代换法、递归树法、主方法更是后面动态规划、图算法复杂度推导的通用工具。这一层没打牢后面看红黑树删除、斐波那契堆分析就会全程卡壳。2.1 渐进记号O、Ω、Θ 到底在比较什么很多人背下了“O 是上界、Ω 是下界、Θ 是紧确界”但一到题目里就分不清该用哪个。关键在于理解它们描述的是函数集合而不是某个具体运行时间。第四版第 3 章把形式化定义单独列了一节就是为了纠正“凭感觉写复杂度”的习惯。记号含义常见误用O(f(n))渐近上界存在常数 c、n₀ 使 0 ≤ g(n) ≤ c·f(n)把 O 当成“最坏情况”的同义词Ω(f(n))渐近下界认为 Ω 只用于最好情况Θ(f(n))上下界同时成立紧确界把 Θ 和 O 混用写“平均 O(n)”o(f(n))严格上界g(n)/f(n) → 0和 O 混为一谈梳理下来会发现最容易错的是把“最坏情况”和“上界”画等号。最坏情况是输入层面的描述O 是函数增长层面的描述两者维度不同。做题时先问自己我要表达的是“不会超过”还是“恰好这个量级”前者用 O后者用 Θ。2.2 递归式三件套代换、递归树、主方法分治算法的复杂度几乎都以递归式出现第四版第 4 章给了三种解法各有适用边界。代换法靠猜加归纳证明适合验证已知答案递归树法直观适合找猜测主方法最快但有形式限制。# 主方法判定框架T(n) a·T(n/b) f(n) # 比较 f(n) 与 n^(log_b a) 的量级 import math def master_method(a, b, f_exponent): critical math.log(a, b) # 临界指数 log_b(a) if f_exponent critical: return fTheta(n^{critical:.2f}) # 情况1叶子主导 elif f_exponent critical: return fTheta(n^{critical:.2f} * log n) # 情况2均衡 else: return fTheta(n^{f_exponent}) # 情况3根主导需正则条件这段代码把主方法的三种情况压缩成一个判定先算临界指数 log_b(a)再和 f(n) 的指数比大小。参数 a 是子问题个数b 是规模缩小比例f_exponent 是合并代价的指数。注意情况 3 还要求正则条件 a·f(n/b) ≤ c·f(n) 成立考试里经常有人漏掉这一步直接下结论。递归树法适合主方法不适用时比如子问题规模不等代换法则用于验证——三种方法不是替代关系而是互补。提示遇到 T(n) 2T(n/2) n log n 这类 f(n) 带对数的主方法情况 2 的扩展形式才管用别硬套基础版。3. 排序与数据结构从比较排序下界到平衡树第二部分和第三部分合起来是全书最“应试”的模块堆排序、快速排序、线性时间排序、哈希表、二叉搜索树、红黑树。这一块的重点不是背算法步骤而是理解每条设计选择的代价——为什么快排要随机化、为什么哈希表最坏情况会退化、为什么红黑树插入删除要旋转。复习时把“操作—复杂度—触发条件”三者绑在一起记比单独背结论有效得多。3.1 比较排序的下界与线性时间排序的适用条件第 8 章先证明了一个反直觉的结论任何比较排序在最坏情况下至少要 Ω(n log n) 次比较。这个下界来自决策树模型——n 个元素的排列有 n! 种决策树高度至少 log(n!) Θ(n log n)。正因为有这个天花板计数排序、基数排序、桶排序才必须“绕过比较”代价是对输入分布或取值范围有假设。算法时间复杂度前提假设稳定性计数排序Θ(n k)元素为 0~k 的整数稳定基数排序Θ(d(n k))按位排序d 位数稳定桶排序期望 Θ(n)输入均匀分布视实现最容易踩的坑是忽略前提计数排序的 k 如果远大于 n复杂度反而退化桶排序的“期望线性”依赖均匀分布假设输入偏斜时直接翻车。考试里问“为什么不用计数排序排浮点数”答案就是它要求整数键。3.2 红黑树五条性质与旋转的复习抓手红黑树是数据结构部分的难点第四版第 13 章把插入和删除分开讲删除部分尤其绕。复习时不要试图背下所有情形而是抓住五条性质节点非红即黑、根为黑、叶 nil 为黑、红节点子节点必黑、任一点到叶的黑高相同和两个旋转操作其余都是为恢复性质服务的。# 红黑树插入后的修复逻辑伪代码级梳理 # 新节点染红 - 若父节点为红则违反性质4 # 情形1叔叔为红 - 父与叔染黑祖父染红上移检查 # 情形2叔叔为黑且当前节点是右孩子 - 左旋父节点转为情形3 # 情形3叔叔为黑且当前节点是左孩子 - 父染黑祖父染红右旋祖父这段注释把插入修复的三种情形串成一条链情形 1 只做颜色调整并上移情形 2 通过旋转转成情形 3情形 3 旋转加染色后终止。参数上要盯住“叔叔节点的颜色”它是分支判断的唯一依据。删除修复更复杂但逻辑同源——先看兄弟颜色再看兄弟孩子颜色四种情形互相转化。血泪经验是手写红黑树删除时先画一棵最小合法树三到四个节点逐步模拟比对着文字描述空想靠谱得多。注意红黑树的“黑高”性质是理解它为什么平衡的关键复习时用一句话自测——从根到任意叶的最长路径不超过最短路径的两倍能推出来就说明真懂了。4. 高级设计与分析动态规划、贪心与摊还第四部分是全书的策略核心动态规划、贪心算法、摊还分析。这三者经常被混为一谈实际上回答的是不同问题——动态规划解决“子问题重叠”贪心解决“局部最优可导出全局最优”摊还分析解决“单次操作贵但总体便宜”。复习这一块重点在于判断“什么时候该用哪种”而不是把每个例题的递推式背下来。4.1 动态规划最优子结构与重叠子问题的识别第 14 章从钢条切割讲到矩阵链乘、最长公共子序列、最优二叉搜索树例题虽多套路一致刻画最优解结构、递归定义最优值、自底向上计算、重构解。判断一道题能不能用动态规划看两个条件——最优子结构最优解包含子问题最优解和重叠子问题递归会重复计算。# 最长公共子序列二维 DP 的典型骨架 def lcs(X, Y): m, n len(X), len(Y) # c[i][j] 表示 X[:i] 与 Y[:j] 的 LCS 长度 c [[0] * (n 1) for _ in range(m 1)] for i in range(1, m 1): for j in range(1, n 1): if X[i-1] Y[j-1]: c[i][j] c[i-1][j-1] 1 # 字符匹配斜向加一 else: c[i][j] max(c[i-1][j], c[i][j-1]) # 取上方或左方较大者 return c[m][n]这段代码里 c[i][j] 的状态定义是核心它表示前缀的 LCS 长度而不是整个串。参数 i、j 从 1 开始遍历对应第四版伪代码的 1-origin 习惯书里明确说过数组常从 1 开始移植到 0-origin 语言时要么减一要么多开一格。最容易错的地方是状态定义含糊——写递推式之前先用一句话说清 dp 数组每一项代表什么否则边界条件必错。4.2 贪心与摊还正确性证明和势能函数贪心算法的难点不在实现在证明。第 15 章的活动选择问题用“贪心选择性质”加“最优子结构”两步证明Huffman 编码则用交换论证。复习时记住贪心不是“看起来对就行”必须能说明“存在一个最优解包含贪心选择”。摊还分析三种方法里聚合分析最直观记账法靠“存款”直觉势能法最形式化但最通用——动态表的扩容分析就是势能法的标准例题。方法核心思想适合场景聚合分析算 n 次操作总代价再平均操作序列规律明显记账法给便宜操作预存“信用”贵操作可被前面的操作摊平势能法定义势函数 Φ摊还代价 实际代价 ΔΦ需要严格证明时梳理下来会发现摊还分析和平均情况分析是两回事前者是对最坏操作序列的保证后者依赖输入分布。这个区分在选择题里反复出现别搞混。5. 图算法与专题最短路径、最大流到 NP 完全性第五到第七部分是全书分量最重的部分图算法BFS/DFS、最小生成树、单源与全对最短路径、最大流、二分图匹配、专题并行、在线、矩阵运算、线性规划、FFT、数论、字符串匹配、机器学习、NP 完全性、近似算法。这一块知识点密集但主线清晰——图算法围绕“遍历、松弛、增广”三个动作展开专题部分则各自独立按需复习即可。5.1 最短路径家族Bellman-Ford、DAG、Dijkstra、Floyd-Warshall第 22、23 章把最短路径算法按“边权是否有负、是单源还是全对”排成一张表复习时按这张表记最省力。核心操作是松弛若 d[v] d[u] w(u,v) 则更新 d[v]。不同算法的差别在于松弛的顺序和次数。算法适用条件复杂度关键点Bellman-Ford可有负权可检测负环O(VE)松弛 V-1 轮再查一轮判负环DAG 最短路径有向无环图O(VE)按拓扑序松弛一次Dijkstra非负权O((VE)lgV) 用斐波那契堆贪心选最近点不能有负边Floyd-Warshall全对可有负权O(V³)三重循环中间点在外层最容易翻车的是 Dijkstra 遇到负权边——它不是“可能出错”而是必然出错因为贪心选择的前提被破坏。另一个易漏点是 Floyd-Warshall 的循环顺序中间点 k 必须放最外层放错位置结果就错这个细节考试里坑过不少人。5.2 最大流与二分图匹配增广路径的统一视角第 24、25 章把最大流和二分图匹配放在一起讲是因为它们共享“增广”思想。Ford-Fulkerson 方法不断在残量网络里找增广路径直到找不到为止二分图最大匹配可以归约为最大流加源点和汇点边容量为 1。第四版新增的第 25 章还讲了稳定婚姻问题和匈牙利算法把匹配问题从“最大”扩展到“稳定”和“带权最优”。# 残量网络增广的核心逻辑Edmonds-Karp 用 BFS 找增广路 def bfs_augment(graph, source, sink, parent): visited {source} queue [source] while queue: u queue.pop(0) for v, cap in graph[u].items(): if v not in visited and cap 0: # 残量大于0才可走 visited.add(v) parent[v] u if v sink: return True queue.append(v) return False这段 BFS 找增广路的代码里cap 0 是唯一通行条件——残量网络里边权表示“还能推多少流”。参数 parent 记录路径用于回溯更新残量。Edmonds-Karp 用 BFS 而非 DFS保证复杂度为 O(VE²)这是它比朴素 Ford-Fulkerson 强的地方。易错点是增广后要同时更新正向边和反向边反向边容量增加漏掉反向边就再也找不到可回退的路径。5.3 NP 完全性与近似算法归约链怎么记第 34、35 章是理论部分的重头戏。NP 完全性的复习不要试图背下所有问题的证明而是记住一条经典归约链SAT → 3-CNF-SAT → 团问题 → 顶点覆盖 → 哈密顿回路 → 旅行商问题。每个归约的方向和多项式时间可验证性是考点。近似算法则回答“NP 难问题怎么办”——顶点覆盖的 2-近似、集合覆盖的贪心 ln n 近似、子集和的完全多项式时间近似方案FPTAS重点记近似比和证明思路。提示判断一个问题是否 NP 完全先看它能不能多项式时间验证属于 NP再看能不能从已知 NP 完全问题归约过来。两步缺一不可。6. 易错点清单那些复习时最容易漏掉的细节这一章单独把高频翻车点拎出来每条按“易漏点 → 为什么漏 → 怎么补”写复习到最后阶段对照过一遍比重新翻书效率高。易漏点一渐进记号的“最坏情况”混淆。为什么漏教材里 O 常和“最坏”一起出现形成惯性联想。怎么补做题时强制写出“这是对函数增长的上界描述”遇到“平均 O(n)”这种写法直接判错平均情况要用 Θ 或明确写期望。易漏点二主方法情况 3 的正则条件。为什么漏三种情况的判定公式太好记正则条件 a·f(n/b) ≤ c·f(n) 常被跳过。怎么补每次用情况 3 前多写一行验证尤其是 f(n) 增长较快但带振荡的题。易漏点三红黑树删除的双黑修复。为什么漏插入修复只有三种情形删除修复有四种且互相转化文字描述长容易只看不练。怎么补拿最小合法树手推一遍“兄弟为黑、兄弟孩子一红一黑”的情形画图比读文字有效。易漏点四Dijkstra 与负权边。为什么漏平时练习的图大多非负负权只在 Bellman-Ford 章节出现。怎么补记住一句判据——只要图里有负边Dijkstra 直接出局改用 Bellman-Ford 或 Johnson。易漏点五摊还分析与平均情况分析混用。为什么漏两者都涉及“平均”字眼。怎么补摊还是对操作序列的最坏保证不依赖概率平均情况依赖输入分布。动态表扩容是摊还哈希表查找是平均别对调。7. 复习路线与查漏补缺一份可执行的清单复习《算法导论》第四版最忌从头到尾线性刷。更有效的做法是按“基础 → 排序与结构 → 设计策略 → 图算法 → 专题”分五轮每轮只抓该层的主线最后用错题反查薄弱模块。下面这份清单可以直接抄进笔记软件按周打勾。轮次覆盖章节自测标准建议时长第一轮第 1~4 章能手推插入排序最坏情况、独立解出主方法三类递归式1 周第二轮第 6~13 章能说清快排随机化的理由、手画红黑树插入修复2 周第三轮第 14~16 章能判断 DP 与贪心的适用边界、写出摊还势能分析1.5 周第四轮第 20~25 章能默写四种最短路径的适用条件、解释增广路径2 周第五轮第 26~35 章按需选读重点记 NP 归约链和近似比1 周查漏补缺的具体技巧每轮结束后从书后 931 道练习里挑该章标星★的题做三道做不出来就回到对应小节重读分析过程而不是直接看答案。第四版把研究生向的内容标了星本科生复习可以跳过但备考深度较大的考试时标星小节往往是区分度所在。另一个习惯是给每个算法建一张“三行卡片”——一行写适用条件一行写复杂度一行写一个反例或易错点考前只翻卡片不翻书。我自己的教训是第一遍学图算法时觉得 Dijkstra 最简单结果模拟题里一道带负权边的变形直接翻车从那以后我每次复习最短路径都强制走一遍“边权符号 → 单源还是全对 → 选算法”的判定流程再也不敢凭印象选。希望这份梳理能帮到你把这本书从“翻过”变成“真的会”。本文还有配套的精品资源点击获取
