简介：《算法导论》英文原版（第三版）PDF 教材，面向计算机专业学生、算法学习者及准备技术面试与考研的读者，用于系统建立算法设计与分析的知识框架。压缩包内仅 1 个 PDF 文件，约 5.12MB，完整收录 MIT Press 第三版正文，包含前言、目录与索引，便于按章节检索和离线阅读。已有 640 人学习下载。全书 34 章，从算法在计算中的角色、插入排序与增长函数讲起，依次展开分治法、概率分析与随机化算法、堆排序与快速排序、线性时间排序、哈希表与二叉搜索树，并深入动态规划、贪心算法、图算法、回溯法及 NP 完全性等主题；每章配有伪代码、正确性论证与复杂度分析，适合课堂学习、刷题复盘和面试前查漏补缺。
1. 知识地图：34 章怎么切成四层，先看哪条线
《算法导论》英文原版最厚的部分，其实是它坚持用同一套数学语言把「代价」讲清楚：前面用渐进记号定义什么叫快，后面才拿这把尺子去量排序、树、图和最优化问题。全书 8 个部分、34 章，957 道节末练习加 158 道章末问题，带星号的段落属于研究生难度。它的知识地图其实只有四条主线：分析工具、数据结构的取舍、设计范式、图与难解性。这本教材适合已经会写递归、学过归纳法证明的人系统过一遍，也适合备考时按模块查漏补缺——原版最大的好处是术语和记号跟课程讲义、论文完全对得上，不会被二手译名绕晕。
2. 基础层三件套：渐进记号、递归式与循环不变式
这一层是全书的语法。后面每一章都在重复同一个动作：先用循环不变式或归纳法说清算法为什么对，再用递归式或求和算出它多贵，最后用渐进记号把常数扔掉。三件套里任何一件没吃透，读到红黑树删除和主定理证明那一节就会直接卡住。
2.1 循环不变式：把「算法对不对」写成三段论
书里证明正确性几乎只用一种模板：找出循环每一轮开始时都成立的那句话，然后分三步走——初始化（第一次进入循环前成立）、保持（这一轮成立，下一轮仍成立）、终止（循环结束时，不变式加上终止条件正好推出我们要的结论）。插入排序是最干净的样例：不变式是「每轮开始时，前 j-1 个元素是原数组前 j-1 个元素的一个有序排列」。
def insertion_sort(a): # 不变式：每轮外层循环开始时，a[0..j-1] 是原数组前 j 个元素的有序排列 for j in range(1, len(a)): key = a[j] i = j - 1 while i >= 0 and a[i] > key: # 用严格大于，相等元素不后移，保证稳定 a[i + 1] = a[i] i -= 1 a[i + 1] = key return akey保存当前待插入元素，i是已排序区间的右边界。a[i] > key这一处决定了稳定性：改成>=之后，相等元素会被交换位置，排序就从稳定变成不稳定。代价上，最坏情况（逆序）比较次数是 n(n-1)/2，属于 Θ(n²)，最好情况（已有序）只比较 n-1 次，属于 Θ(n)——同一个算法两个界，这也是后面讲「平均情况」和「最坏情况」要分开的原因。
最容易跳过的是第三步。很多人写证明只写到「保持」就停了，但终止那一刻j = n且i停在了正确位置，才把「前 n 个元素有序」这个结论真正落地。少了这一步，证明只是说明循环没崩，没说明算法完成了任务。
2.2 渐进记号：O、Θ、Ω 的边界与常见函数
三个记号不是同义词。O 只给上界，允许给得很松（n 属于 O(n²) 是成立的），Θ 要求上界下界同阶，Ω 给下界。写「快排是 O(n log n)」在严格意义上是不准确的，应说期望 Θ(n log n)，最坏 Θ(n²)。书里还给了 o 和 ω 表示严格不等，用来区分「同阶」和「低一阶」。
| 记号 | 含义 | 常见误用 |
|---|---|---|
| O(f(n)) | 存在常数 c、n₀，使 0 ≤ g(n) ≤ c·f(n) | 当成「大约等于」，把上界当紧界 |
| Ω(f(n)) | 存在常数 c、n₀，使 0 ≤ c·f(n) ≤ g(n) | 与最好情况混为一谈 |
| Θ(f(n)) | 同时是 O 和 Ω | 只验证一边就下结论 |
| o / ω | 严格低阶 / 严格高阶 | 和 O / Ω 混用 |
常见函数的量级顺序要能背下来：log n < √n < n < n log n < n² < n³ < 2ⁿ < n!。两个细节：对数底数在渐进意义下可忽略，因为 log_a n = log_b n / log_b a 只差常数；但写 Θ 时同一段推导里底数要统一，否则主定理里 n^{log_b a} 会算错。求和公式里最常用的三个是等差求和 n(n+1)/2、几何级数（公比小于 1 时收敛到常数）、调和级数 H_n = Θ(log n)，后者是摊还分析里动态表扩张的关键。
2.3 递归式求解三法：代换法、递归树、主定理
代换法是「先猜后证」：猜出 T(n) ≤ c·n log n，再用归纳法把常数 c 凑出来。它的难点全在常数上——减去低阶项时经常要把 n 缩小到 n - 1 或 n/2 才成立。递归树是把每一层的代价加起来，形状不规则的递归式（比如 T(n) = T(n/3) + T(2n/3) + n）只能靠它。主定理处理 T(n) = aT(n/b) + f(n) 这一类，核心是比较 f(n) 和 n^{log_b a} 谁大：
| 情形 | 条件 | 结论 |
|---|---|---|
| 1 | f(n) = O(n^{log_b a - ε}) | T(n) = Θ(n^{log_b a}) |
| 2 | f(n) = Θ(n^{log_b a}) | T(n) = Θ(n^{log_b a} · log n) |
| 3 | f(n) = Ω(n^{log_b a + ε}) 且满足正则条件 | T(n) = Θ(f(n)) |
第三种情形那个正则条件是 a·f(n/b) ≤ c·f(n)（c < 1），用来排除 f(n) 带震荡因子的情况；书里专门有一节证明主定理，那个证明不必逐行背，但要知道条件不能省。
import random, math cnt = 0 def merge_sort(a): global cnt if len(a) <= 1: return a mid = len(a) // 2 left, right = merge_sort(a[:mid]), merge_sort(a[mid:]) out, i, j = [], 0, 0 while i < len(left) and j < len(right): cnt += 1 # 每次元素比较记一次，对应递归式里的 Θ(n) if left[i] <= right[j]: # 用 <= 保持稳定 out.append(left[i]); i += 1 else: out.append(right[j]); j += 1 return out + left[i:] + right[j:] for n in (1024, 2048, 4096): cnt = 0 merge_sort([random.random() for _ in range(n)]) print(n, cnt, round(cnt / (n * math.log2(n)), 3))这段代码用实测比较次数验证 T(n) = 2T(n/2) + Θ(n) 的解是 Θ(n log n)：cnt / (n·log₂n)在三组规模下都稳定在 1 附近的常数上，说明增长量级吻合。cnt用global是因为递归里要累加，实际工程代码应该包成类或传可变容器。参数换成不同的 n，比值波动不超过 20% 就足够说明问题——这比背结论更有说服力，也是查漏补缺时验证自己有没有把递归式列错的最快办法。
3. 排序与数据结构：比较下界、散列冲突与平衡树的取舍
排序部分是整本书的「实验田」：几乎所有分析技巧都先在这里演练一遍。数据结构部分则反过来，讲的是同一个抽象类型（有序集合、优先队列、字典）在不同约束下该选哪种实现，选错的代价通常体现在常数和 I/O 上，而不是量级上。
3.1 比较排序的下界：决策树为什么卡在 Ω(n log n)
书里用决策树证明：任何只靠元素两两比较来确定顺序的算法，对应一棵有 n! 个可达叶子的二叉树，高度至少 log₂(n!)。用斯特林公式展开得到 Ω(n log n)。这个结论的适用范围常被误读——它约束的是「比较模型」，一旦算法利用了元素本身的数值结构（计数、基数、桶），下界就失效了。所以线性时间排序不是打破了下界，而是换了模型。
顺带一个常考的推论：n 个元素中找最大值至少需要 n-1 次比较，同时找最大和最小需要 ⌈3n/2⌉ - 2 次。这类「下界 + 达到下界的构造」是证明题的高频套路。
3.2 线性时间排序：三种方法的适用边界
| 算法 | 时间 | 额外空间 | 稳定 | 前提条件 |
|---|---|---|---|---|
| 计数排序 | Θ(n + k) | Θ(n + k) | 是 | 关键字是 0..k 的整数，k 不能远大于 n |
| 基数排序 | Θ(d(n + k)) | Θ(n + k) | 是 | 按位排序，每一位用稳定子排序 |
| 桶排序 | 平均 Θ(n) | Θ(n) | 视实现 | 输入均匀分布在 [0,1)，最坏 Θ(n²) |
三个都稳定，这点不能丢：基数排序的正确性完全依赖子排序稳定，把计数排序换成快排，基数排序立刻出错。计数排序的空间是 O(k)，当 k = O(n) 时才真正线性，遇到值域极大的数据要先用坐标压缩。
3.3 散列表：链接法与开放寻址的取舍
链接法把冲突元素挂成链表，装填因子 α = n/m 可以大于 1，成功查找的期望代价是 Θ(1 + α)。开放寻址把元素都存在表内，α 必须小于 1，探测序列有线性探测、二次探测和双重散列三种，成功查找的期望探测次数约为 (1 + 1/(1-α))/2。线性探测的「一次聚集」会让长连续段越滚越大，实践中 α 超过 0.7 性能就开始明显下降。
DELETED = object() # 删除标记：不能直接置 None，否则会切断探测链 class OpenHash: def __init__(self, m): self.m, self.t = m, [None] * m def probe(self, k, i): return (k + i) % self.m # 线性探测，第 i 次尝试 def insert(self, k): for i in range(self.m): j = self.probe(k, i) if self.t[j] is None or self.t[j] is DELETED: self.t[j] = k return j raise OverflowError("表已满，需要扩容") def search(self, k): for i in range(self.m): j = self.probe(k, i) if self.t[j] is None: # 遇到真正的空位才停止探测 return None if self.t[j] is not DELETED and self.t[j] == k: return j return NoneDELETED哨兵是这段代码唯一的重点：直接删除后置None，查找会在半路提前终止，后面的元素永远找不到。这是散列章节最经典的易错点，考试和面试都爱考。参数m一般取质数或 2 的幂配合位运算，扩容时通常翻倍并重新散列全部元素，这一步的摊还代价是 O(1)。
3.4 平衡树的取舍：红黑树旋转、B 树与增广结构
二叉搜索树的查找、插入、删除都是 O(h)，h 在随机建树时期望 O(log n)，但有序插入会退化成链。红黑树用五条性质把高度锁死在 2log(n+1)：节点非红即黑、根黑、叶子（NIL）黑、红节点的子节点必黑、任一点到叶子的路径上黑高相同。插入修正分三种情况，删除修正分四种，关键操作是旋转：
def left_rotate(tree, x): y = x.right x.right = y.left # y 的左子树挂到 x 右边 if y.left: y.left.parent = x y.parent = x.parent # y 顶替 x 的位置 if x.parent is None: tree.root = y elif x is x.parent.left: x.parent.left = y else: x.parent.right = y y.left = x x.parent = y旋转只改指针，代价 Θ(1)。插入修正最多两次旋转就能收尾，删除修正最多三次，所以插入删除整体仍是 O(log n)。B 树换了个思路：每个节点存 2t-1 到 t-1 个关键字，把树高压到 O(log_t n)，专门为磁盘页设计——一次节点访问等于一次磁盘读，减少层数比减少比较次数重要得多。增广数据结构则是在节点上加附加域（子树规模、区间最大值），用它做顺序统计和区间重叠查询，前提是增广后旋转仍能 O(1) 维护该域。
4. 设计范式主线：动态规划、贪心、摊还与最短路
这一章是全书的枢纽。分治、动态规划、贪心回答「怎么想出算法」，摊还回答「怎么给一串操作算总账」，图算法则是这些范式最密集的应用场。复习时把这几块串起来看，比单独背每个算法的复杂度有效得多。
4.1 动态规划：最优子结构、重叠子问题与两种方向
动态规划的四步是固定的：刻画最优解的结构、递归地定义最优值、自底向上算出最优值、用记录表回溯出解。判定能不能用 DP 的关键不是「看起来像」，而是两个性质同时成立——最优子结构（子问题的最优解能拼出原问题的最优解）和重叠子问题（递归树里有大量重复节点）。缺了第二个，分治就够了；缺了第一个，只能上搜索。
def rod_cut(prices, n): # best[j] 表示长度 j 的钢条最大收益，cut[j] 记录第一刀切在哪 best = [0] * (n + 1) cut = [0] * (n + 1) for j in range(1, n + 1): q = -1 for i in range(1, j + 1): if prices[i - 1] + best[j - i] > q: q = prices[i - 1] + best[j - i] cut[j] = i # 记录决策，方便重构方案 best[j] = q return best[n], cutprices[i-1]是长度 i 的价格，内层循环枚举第一刀的位置，cut数组是为了在 O(n) 时间内还原切割方案——只算最大值不记录决策，是初学 DP 最常见的半成品。时间 Θ(n²)，空间 Θ(n)。同一套结构换成二维就是矩阵链乘法和最长公共子序列，区别只在于状态维度和枚举顺序。
| 范式 | 子问题关系 | 决策方式 | 典型题 |
|---|---|---|---|
| 分治 | 互不相交 | 递归后合并 | 归并排序、Strassen |
| 动态规划 | 重叠 | 枚举所有选择取最优 | 钢条切割、LCS、最优二叉搜索树 |
| 贪心 | 重叠但可局部定 | 只取当前最优，不回溯 | 活动选择、Huffman、MST |
4.2 贪心与摊还：交换论证、拟阵、三种摊还方法
贪心要证两件事：贪心选择性质（存在一个最优解包含当前贪心选择）和最优子结构。标准证法是交换论证——把最优解里的某个元素换成贪心选的，证明不会变差。书里用拟阵给了一个更强的框架：如果问题能构成拟阵，按权排序后贪心必得最优，这也是 Kruskal 正确性的来源。反例同样重要：0-1 背包按单位价值贪心会错，分数背包才对，因为前者不满足贪心选择性质。
摊还分析回答的是「最坏的一串操作平均下来多贵」，和平均情况分析完全不同——它不假设输入分布，只对操作序列本身算账。聚合分析算总账除以次数；记账法给每种操作定一个摊还代价，把余额存进数据结构；势能法定义势函数 Φ，摊还代价 = 实际代价 + ΔΦ。动态表扩张是最经典的例子：每次满了就翻倍，插入的摊还代价是 O(1)，尽管单次扩容是 Θ(n)。
| 方法 | 核心 | 适合场景 |
|---|---|---|
| 聚合分析 | 算 n 次操作的总代价再平均 | 操作类型少且规律 |
| 记账法 | 提前多收「存款」付未来的账 | 有明确的「贵操作」 |
| 势能法 | 定义 Φ，摊还 = 实际 + ΔΦ | 需要严格界、结构复杂 |
4.3 图算法四条主线：遍历、生成树、单源最短路、全对最短路
图的表示先要选对：邻接表空间 Θ(V + E)，适合稀疏图；邻接矩阵 Θ(V²)，适合稠密图或需要 O(1) 判断邻接的场合。BFS 按层扩展，能求无权图最短路并生成广度优先树；DFS 打时间戳 d[u]/f[u]，据此把边分成树边、后向边、前向边和横跨边，拓扑排序和强连通分量都建立在它上面——拓扑排序就是按 f[u] 降序排列，SCC 则要用转置图再跑一遍 DFS。
| 算法 | 复杂度 | 负权边 | 适用 |
|---|---|---|---|
| Bellman-Ford | O(VE) | 支持，可判负环 | 一般单源最短路 |
| DAG 单源 | O(V + E) | 支持 | 有向无环图，按拓扑序松弛 |
| Dijkstra（二叉堆） | O((V + E) log V) | 不支持 | 非负权 |
| Floyd-Warshall | Θ(V³) | 支持（无负环） | 全对最短路、稠密图 |
| Johnson | O(V² log V + VE) | 支持 | 稀疏图全对最短路 |
Dijkstra 的正确性依赖一个前提：一旦顶点出队，它的最短距离就确定了。负权边会打破这个前提，因为后面可能出现更短的路径，所以「Dijkstra 加个负权判断」这种改法是无效的，只能换 Bellman-Ford。
import heapq def dijkstra(adj, s): dist = {u: float('inf') for u in adj} dist[s] = 0 pq = [(0, s)] # (当前距离, 顶点) while pq: d, u = heapq.heappop(pq) if d > dist[u]: # 过期条目直接丢弃，等价于 decrease-key continue for v, w in adj[u]: if dist[u] + w < dist[v]: # 松弛 dist[v] = dist[u] + w heapq.heappush(pq, (dist[v], v)) return distadj是邻接表{u: [(v, w), ...]}，s是源点。Python 的堆不支持 decrease-key，所以用「重复入堆 + 过期跳过」模拟，每条边最多入堆一次，总复杂度仍是 O((V+E) log V)。if d > dist[u]这一行删掉不影响结果正确性，但会让复杂度退化，属于典型的能跑但慢的写法。
4.4 最大流与 NP 完全：建模与归约的入口
流网络满足容量约束和流量守恒，残量网络上的增广路径决定了还能推多少流。最大流最小割定理说的是：最大流的值等于最小割的容量，这条定理把优化问题和划分问题连在一起。Ford-Fulkerson 的复杂度依赖容量大小（整数容量时是 O(E|f*|)），改成 BFS 找增广路就是 Edmonds-Karp，O(VE²)。二分图最大匹配可以建成源点连左部、左部连右部、右部连汇点的单位容量网络来求。
NP 完全部分最容易学歪。P 是多项式时间可解，NP 是多项式时间可验证，NPC 是 NP 里「最难」的那批——所有 NP 问题都能多项式归约到它。证明某问题 NPC 的方向是固定的：先证它属于 NP（给一个证书能在多项式时间验证），再把一个已知 NPC 问题归约到它。方向反了就等于什么都没证。经典链条是 SAT → 3-SAT → 团 / 顶点覆盖 / 哈密顿回路。遇到 NPC 问题，实战里只有三条路：问题规模小用指数算法、加约束降成多项式特例、接受近似比 ρ(n) 的近似算法（顶点覆盖有 2 近似，满足三角不等式的 TSP 有 2 近似，子集和有 FPTAS）。
5. 易错点：五处背得出却用不出来的地方
这一章是我自己踩过、也见过别人反复踩的坑。共同点是：结论背得很熟，但条件、方向或前提一丢，写出来的东西就是错的，而且错得很像对的。
易错点一：主定理的三种情形乱套，忽略正则条件。为什么漏：多数人只记「比较 f(n) 和 n^{log_b a}」，看到相等就往第二种情形上套，忘了情形三还要满足 a·f(n/b) ≤ c·f(n)。怎么补：每次套主定理前先写出 a、b、f(n) 三个量，算出 log_b a 的数值再比较，情形三必检正则条件；遇到 f(n) 带 log 因子或震荡因子，直接退回递归树。
易错点二：把随机化快排说成「最坏 O(n log n)」。为什么漏：随机化只把最坏情况的概率压到极低，并不消除它，最坏仍是 Θ(n²)（每次划分都极不均衡）。怎么补：表述固定成「期望 Θ(n log n)，最坏 Θ(n²)，且最坏情况依赖随机数的坏运气」；分析时用指示器随机变量算期望比较次数，那套推导本身也是考点。
易错点三：摊还分析当成平均情况分析。为什么漏：两者都带「平均」的味道，但摊还分析不假设输入分布，它给的是任意操作序列的保底上界。怎么补：做摊还题时明确写出「不涉及概率」，用势能法就老老实实定义 Φ，验证 Φ 非负、初值为 0；动态表那张表要把扩容前后的势能变化算清楚。
易错点四：散列开放寻址删除直接置空，或者 α 取到 1。为什么漏：链地址法删除就是摘链，习惯带过来就出事；α 接近 1 时线性探测的探测次数会爆炸，但代码在小数据上依然能跑通。怎么补：删除用 DELETED 哨兵，查找遇到 DELETED 继续、遇到 None 才停；装填因子控制在 0.5～0.7，超了就扩容重散列。
易错点五：NP 完全证明的归约方向写反。为什么漏：「把这个问题归约到 SAT」读起来也通顺，但方向反了证的是「它不比 SAT 难」，毫无意义。怎么补：写证明时先在纸上画箭头，已知 NPC 问题 → 待证问题，并检查两个方向的时间都是多项式；归约的构造要能双向映射解，只证一边是常见的失分点。
6. 复习清单：三轮查漏补缺与一张自测表
我自己的做法是把 34 章压成三轮，每轮目标不同，不追求一次读懂。
第一轮只做「能复述」：合上书，用白纸画出四条主线的骨架——分析工具（不变式、渐进记号、递归式三法）、数据结构（散列、BST、红黑树、B 树、并查集）、设计范式（分治、DP、贪心、摊还）、图与难解性（遍历、MST、最短路、最大流、NPC 与近似）。画不出来的那一支，就是当天要重读的章节。
第二轮做「能推导」：挑十来个必须手推的点，包括主定理三种情形各一例、红黑树插入的三种修正、钢条切割的状态转移、Dijkstra 与 Bellman-Ford 的正确性条件、最大流最小割的等价性、SAT 到 3-SAT 的归约。每个点不看书写一遍，写完再对照，错的地方标红。
第三轮做「能选型」：拿一张表把算法按场景对照一遍，重点不是复杂度数字，而是「什么条件下不能用」。
| 场景 | 首选 | 必须确认的前提 |
|---|---|---|
| 整数关键字、值域 O(n) | 计数排序 / 基数排序 | 稳定性是否被后续步骤依赖 |
| 字典查询、内存表 | 散列表（链接或开放寻址） | 装填因子、删除是否频繁 |
| 有序动态集合 + 范围查询 | 红黑树 / 增广结构 | 附加域能否 O(1) 维护 |
| 磁盘上的索引 | B 树 | 最小度数 t 与页大小的匹配 |
| 有权图单源最短路 | Dijkstra（非负）/ Bellman-Ford（含负权） | 是否存在负权边、能否判负环 |
| 稀疏图全对最短路 | Johnson | 先跑一次 Bellman-Ford 重赋权 |
| 判定问题太难 | 近似算法 / 特例降维 | 近似比与问题约束是否成立 |
查漏补缺环节，我更信「用输出倒逼输入」：把每个模块讲给一个假想的听众，讲到卡壳的地方立刻回去翻原版对应小节，而不是翻笔记。原版的好处在这里体现得最明显——索引和记号统一，翻回去能立刻定位到定义，不会因为在几个译名之间来回切换而浪费时间。
从那以后，我每次复习都强制走一遍「白纸画骨架 → 手推关键证明 → 按场景选型」这三步，宁可少刷题，也不跳过骨架那一步，因为翻车往往不是因为不会某个算法，而是因为脑子里那张图缺了一角。这份英文原版教材的完整目录、带星号的分层和成套练习，正好能当这三轮的对照底本，需要的可以拿去按章节慢慢啃。希望帮到你。
本文还有配套的精品资源，点击获取
技术演进与工程实践)
