简介《算法导论》英文原版教材第三版面向计算机专业学生、考研复试与算法面试备考者以及希望系统补齐算法基础的开发者用一部权威教材把算法设计和复杂度分析串联成完整知识链路。压缩包内只含 1 个 PDF 文件体积约 5.12MB轻便易携带可在电脑、平板或电纸书上随时翻阅打开全文和目录索引也无需逐级解压。全书 34 章从插入排序、分治与递归式求解讲起覆盖堆排序、快速排序、线性时间排序、哈希表与二叉搜索树等数据结构再延伸至动态规划、贪心算法、摊还分析与图算法并以概率分析和随机化算法等进阶专题收束并配有大量伪代码、练习与思考题。目前已有 640 人学习下载适合按章节精读、配合课程做习题也适合作为查阅复杂度记号与经典算法正确性证明的案头参考。1. 伪代码不绑定语言一本算法教材把「算法」从实现里剥出来的代价翻开这份英文原版教材第一反应通常是意外一本讲算法的书通篇找不到一行能直接运行的代码所有过程都用一套并不存在的伪代码写成。正是这个设计让插入排序、红黑树、动态规划这些概念在几十年后仍能被直接翻译成任何语言。它要解决的核心问题并不是“怎么写代码”而是把算法从实现细节里剥离出来只留下两个可验证的内核渐近复杂度与数据结构维持的不变量。前者回答“规模变大后代价怎么涨”后者回答“每一步操作之后哪些性质必须仍然成立”。抓住这两条主线全书八个部分就会从章节堆叠变成一条推演链每种设计范式都在说明它在什么条件下成立、边界在哪里。2. 渐近记号与递推式增长率凭什么代替真实运行时间2.1 三个记号是集合不是等号两边的算术教材里最容易读错的一句话是把 Θ(g(n)) 写成“等于”。它其实是一个函数集合存在正常数 c₁、c₂ 和 n₀使得所有 n ≥ n₀ 都满足 0 ≤ c₁·g(n) ≤ f(n) ≤ c₂·g(n)才记 f(n) Θ(g(n))。也就是说 Θ 给出的是“上下都被夹住”的紧界。O 只保留上界那一半Ω 只保留下界那一半小 o 和小 ω 则是严格版本——不是“小于等于”而是“对任意常数 c 都成立”等价于两者比值的极限为 0 或无穷。这套定义最反直觉的地方在于O 与“最坏情况”没有必然关系。说“快速排序是 O(n²)”没错但信息量极低因为 O(n³)、O(2ⁿ) 也都成立真正有讨论价值的是“最坏 Θ(n²)、期望 Θ(n log n)”。搞清楚“界”和“情况”是两个正交的维度是读懂后面所有复杂度分析的前提。极限判据是最实用的判断工具把函数相除取极限即可lim(n→∞) f(n)/g(n)结论等于正常数 cf Θ(g)等于 0f O(g)且 f o(g)等于无穷f Ω(g)且 f ω(g)提示对数底数在渐近意义下无关紧要因为换底只差一个常数因子所以 lg 和 ln 在复杂度里可以混用但指数上的常数不能忽略n^2.807 和 n³ 是两个世界。“忽略常数”这条约定经常被误读成“常数不重要”。它的真实含义是当 n 足够大时增长率更高的项必然主导。工程上 n 常常不够大于是常数会翻车小规模数组上插入排序比归并排序快因为后者有额外的数组分配和拷贝开销。教材在分治一章的习题里就要求算这个切换阈值它不是一个理论玩具而是标准库排序实现里真实存在的 cutoff——低于某个长度就直接走插入排序。2.2 递归树与主定理把 T(n)aT(n/b)f(n) 压成三种情形分治算法的代价天然写成递推式规模 n 的问题拆成 a 个规模 n/b 的子问题拆和合的成本是 f(n)。把它画成递归树每一层是当前所有子问题的 f 之和最底下那层有 a^(log_b n) 个叶子。对 a^(log_b n) 做恒等变形就得到 n^(log_b a)——这个数就是整棵树的分水岭也是主定理里唯一需要算的指数。情形一f(n) O(n^(log_b a − ε))ε 0。非递归代价比叶子代价低一个多项式级别总代价由叶子决定T(n) Θ(n^(log_b a))。情形二f(n) Θ(n^(log_b a))。每一层代价相当一共 log_b n 层T(n) Θ(n^(log_b a) · lg n)。更一般地若 f(n) Θ(n^(log_b a) · lg^k n)则结果再多一个 lg 因子。情形三f(n) Ω(n^(log_b a ε))并且存在常数 c 1 使 a·f(n/b) ≤ c·f(n)。代价集中在根T(n) Θ(f(n))。情形三那个附加条件常被跳过但它不是装饰。它保证每层代价按几何级数衰减否则“根主导”的结论不成立。以 T(n) 2T(n/2) n² 为例检查一下a·f(n/b) 2·(n/2)² n²/2 ≤ c·n²取 c 1/2 即可条件满足答案 Θ(n²)。三种情形之间还有缝隙。情形一和三都要求 f(n) 与分水岭之间差一个多项式级别那个 ε如果只差一个对数因子主定理直接失效。典型反例是 T(n) 2T(n/2) n/lg n分水岭是 nf(n) 只比它小一个 lg 因子不属于任何情形。这时只能回到递归树手工求和第 i 层总代价约为 n/(lg n − i)从 i 0 累加到 lg n得到 n·H(lg n)最终 T(n) Θ(n·lg lg n)。这类“主定理覆盖不到”的题在教材里是刻意保留的它提醒读者公式有适用边界。主定理之外还有两件工具配合使用。代换法是先猜答案再归纳证明难点在边界条件——归纳过程中经常要多减一个低阶项才能让不等式闭合。递归树法负责给出猜测两者一前一后构成完整的证明链。2.3 把主定理写成可执行的判定器把判定逻辑写成代码比反复翻书更可靠。下面这个函数只处理 f(n) n^p 的形式够覆盖绝大多数教科书例题import math def classify(a, b, p, eps1e-9): 判定 T(n) a*T(n/b) Theta(n**p) 命中主定理的哪种情形。 a: 每层拆出的子问题个数 b: 子问题规模缩小的倍数b 1 p: 非递归部分 f(n) n**p 的指数 eps: 浮点比较容差避免 log 计算误差误判情形二 # 分水岭指数递归树叶子的总规模 n**(log_b a) crit math.log(a) / math.log(b) if p crit - eps: # 叶子主导合并代价比叶子低一个多项式级别 return 情形1, fTheta(n^{crit:.4f}) if abs(p - crit) eps: # 每层同价层数 log_b n 变成一个额外的 lg 因子 return 情形2, fTheta(n^{crit:.4f} * lg n) # 根主导还需要额外验证正则条件 a*f(n/b) c*f(n), c 1 return 情形3, fTheta(n^{p}) cases [ (归并排序, 2, 2, 1), # T(n)2T(n/2)Theta(n) (二分查找, 1, 2, 0), # T(n)T(n/2)Theta(1) (Strassen 矩阵乘, 7, 2, 2), # T(n)7T(n/2)Theta(n^2) (T(n)2T(n/2)n^2, 2, 2, 2), ] for name, a, b, p in cases: print(name, classify(a, b, p))四组参数分别对应四种典型结果。归并排序的 a 2、b 2分水岭是 n¹与 f(n) Θ(n) 持平落进情形二得到 Θ(n lg n)。二分查找的 a 1、b 2分水岭是 n⁰ 1同样持平得到 Θ(lg n)——这也是“情形二不一定带 n”的例子。矩阵乘的 Strassen 变体把 8 次子乘法压到 7 次分水岭变成 n^log₂7 ≈ n^2.807比 f(n) Θ(n²) 高一个多项式级别落进情形一于是从 Θ(n³) 降到 Θ(n^2.807)。最后一组是情形三根主导。参数里最容易填错的是 p。如果 f(n) 带了对数因子比如 f(n) n·lg n就不能简单套 p 1而要按情形二的扩展形式处理结果指数不变、lg 的幂次加一。这是批改作业时最高频的错误之一。3. 数据结构的不变量红黑树、B 树与哈希表各自在守哪条底线3.1 红黑树的五条性质高度如何被锁在 2lg(n1)平衡树的难点不在旋转而在“为什么旋转几次就够”。红黑树给出的答案是一组局部约束每个节点非红即黑根是黑叶节点空指针视为黑红节点的两个孩子都必须是黑从任一节点出发到其所有后代叶子的路径上黑节点数目相同这个数叫黑高 bh。前四条是局部可检查的第五条是全局约束也是整个结构的关键。由“红节点不相邻”可得任一路径上红节点数不超过黑节点数于是最长路径不超过最短路径的两倍。再由黑高归纳可证以某节点为根的子树至少有 2^bh − 1 个内部节点。两式合起来n ≥ 2^(h/2) − 1即高度 h ≤ 2lg(n1)。这就是“查找最多走两倍于理想平衡树的路径”的严格来源。旋转是维持这套约束的唯一手段它只改指针、不改中序序列def left_rotate(tree, x): 对节点 x 左旋右孩子 y 顶替 x 的位置x 变成 y 的左孩子。 y x.right x.right y.left # y 的左子树挂到 x 的右边中序序列不变 if y.left is not None: 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 降为 y 的左孩子 x.parent y整个操作只动三组指针代价 Θ(1)。右旋完全对称。要注意的是旋转本身不改变黑高它只是把“红红相邻”这个局部违规搬到别处真正修复约束的是旋转之后的重新着色。插入时新节点一律染红这样第五条性质自动成立唯一可能被破坏的是“红节点不能有红孩子”。修正分三种情形叔叔节点是红色就把父亲和叔叔染黑、祖父染红违规点上移两层继续处理叔叔是黑色且当前节点是内侧孩子比如父亲是左孩子、自己是右孩子先对父亲旋转把它转成外侧叔叔是黑色且当前是外侧孩子就父染黑、祖父染红对祖父旋转。整个循环最多沿树上升 O(lg n) 层旋转不超过两次。删除要复杂得多。被删节点若为黑色会破坏黑高平衡教材用“额外一层黑色”的概念把问题归约为四种情形其中“兄弟为黑且两个侄子都为黑”的处理是把兄弟染红、额外黑色上推给父节点——这一支最容易漏漏了就会出现某条路径黑高少一的情况查询表面上还能跑但树在慢慢退化。血泪经验是插入删除写完后第一件事是写一个校验函数遍历所有节点检查五条性质并比对黑高跑几千次随机操作再谈性能。B 树是同一种思路在磁盘上的变体。既然一次节点访问就是一次 I/O那就不该优化比较次数而该优化树高把成百上千个键塞进一个页大小的节点最小度数 t 保证每个节点键数在 [t−1, 2t−1] 之间高度便降到 log_t n。局部约束推出全局高度套路和红黑树的黑高完全一致只是代价模型从“比较次数”换成了“页读取次数”。3.2 哈希表装载因子、开放寻址与全域哈希防的是什么哈希表把平均查找压到 Θ(1)代价是把“最坏情况”交给了哈希函数。链接法下n 个元素散到 m 个槽装载因子 α n/m一次不成功查找的期望代价是 Θ(1 α)因为要先算哈希再遍历那条链。α 是常数时就是 Θ(1)这也是扩容阈值的理论依据——实现里常见的 0.75 就来自这里。开放寻址把所有元素都存在表内α 必须严格小于 1。线性探测的成功查找期望约为 (1/2)(1 1/(1−α))α 0.5 时约 1.5 次探测看着很美α 0.9 时变成约 5.5 次插入更糟接近 50 次。这条曲线的陡峭程度解释了为什么生产环境的哈希表宁可用更多内存也不肯把装载因子推高。但真正需要关注的是对抗场景。如果哈希函数是公开且固定的输入又由外部控制那么构造一批全部落到同一槽的键并不困难哈希表退化成链表单次请求从 O(1) 变成 O(n)——这是可被利用的性能塌陷。教材给出的解法是全域哈希设计一族哈希函数每次建表随机选一个使得任意两个不同键冲突的概率不超过 1/m。随机性一旦引入对手就无法预先构造期望代价重新回到 Θ(1α)。这个思路在很多语言运行时的哈希实现里都能看到影子只是具体做法各有取舍。3.3 摊还分析动态表扩容为什么敢算 O(1)动态数组的扩容看起来很贵满了就申请两倍空间把老元素全搬过去。但教材用三种方法证明单次插入的摊还代价是 O(1)。聚合法最直观从空表开始连续插入 n 次总搬运量是 1 2 4 … n/2 n加上 n 次基本插入总代价小于 2n摊到每次就是 O(1)。记账法给每次插入存 3 块钱1 块付自己的插入2 块留给将来搬运自己——扩容时每个老元素正好有 2 块余额可用。势能法最优雅定义势函数 Φ 2·num − size表满时 Φ 达到峰值 size扩容后归零势能的下降恰好支付了搬运成本。三种方法结论一致但适用场景不同。聚合法适合过程规律、能整体求和的场景记账法适合成本可以被“预存”的场景势能法适合能写出一个非负势函数、且操作前后势差可控的场景。选哪种取决于你能否找到那个函数而“找得到”本身就是对结构的理解程度。结构查找插入/删除有序遍历最坏情况保证哈希表期望 Θ(1)期望 Θ(1)不支持依赖哈希族的随机性红黑树Θ(lg n)Θ(lg n)旋转次数常数支持有B 树Θ(log_t n) 次 I/O同左支持有4. 动态规划与贪心状态表在什么条件下可以不要4.1 最优子结构与重叠子问题状态定义决定一切动态规划成立需要两个条件同时具备。最优子结构是说问题的最优解由子问题的最优解拼成重叠子问题说的是递归展开时会反复遇到同一个子问题。分治同样有最优子结构但它的子问题互不相交重复求解不存在所以只需要递归不需要表。真正决定 DP 能否写对的是状态定义。判断标准只有一条状态里必须包含“做下一步决策所需的全部信息”一个都不能少。钢条切割的状态是一维的——长度 n 的最优收益为 r(n) max(p(i) r(n−i))因为剩下的只有长度这一个变量。最长公共子序列的状态是二维的 (i, j)因为“前缀对前缀”这个信息足以决定下一个字符怎么配。一旦题目加了约束维度就得跟着加。比如要求公共子序列必须包含某个字符、或者背包里某类物品至少取一件原来的二维状态就不够用了因为两个不同的历史过程被压进了同一个状态后续决策无法区分。症状很典型答案偏小或偏大而且改成暴力搜索就对改成 DP 就错。提示写 DP 的正确顺序是先写暴力递归观察参数列表里有几个变量再决定维度而不是先画表格再想办法把题目塞进去。4.2 一张表看懂 LCS 的填表顺序最长公共子序列的转移方程只有两行但填表顺序和边界处理决定了实现对不对def lcs_length(x, y): m, n len(x), len(y) # c[i][j] x[:i] 与 y[:j] 的最长公共子序列长度 # 第 0 行和第 0 列全为 0表示任一串为空时公共长度为 0 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]时间 Θ(mn)空间 Θ(mn)。注意 i、j 从 1 开始而字符串下标从 0 开始这个错位是越界错误的高发区写 x[i] y[j] 在 i m 时会直接抛异常。空间可以优化。因为 c[i][j] 只依赖上一行和当前行的左侧用两行滚动数组就能压到 Θ(n)如果连答案都不需要回溯甚至只需要一行加一个临时变量。但代价是丢失完整表格无法反推具体是哪个子序列。这里存在一个真实的取舍要长度还是要方案。工业场景里两者都有需求所以常见做法是先用滚动数组算出长度需要方案时再从末尾回溯重算一遍或者干脆保留全表换取可读性。教材把这种取舍摆在明面上而不是藏着。4.3 贪心的合法性交换论证与拟阵贪心算法便宜但它成立的证明比动态规划严格得多因为要证明“每一步的局部最优选择不会破坏全局最优性”。最通用的证明手法是交换论证假设存在一个最优解它的第一个选择与贪心选择不同构造性地把它换成贪心选择并证明换完之后解不变差——于是总存在一个包含贪心选择的最优解归纳下去就得到贪心的正确性。活动选择问题是这套论证最干净的样本。按结束时间排序每次挑第一个与已选集合兼容的活动。交换时把最优解里第一个活动换成结束最早的那个由于它结束得更早后续可容纳的活动集合只会变大不会变小所以换完仍然最优。更深一层的解释是拟阵。一个带遗传性子集仍独立和交换性两个独立集大小不同时大集合必有一个元素能加进小集合的独立系统配合权函数贪心按权重从大到小挑选就能得到最大权独立集。带截止期和罚款的任务调度可以建成拟阵于是贪心有效而 0-1 背包不能这里没有交换性的结构。0-1 背包 vs 分数背包是最好的反例对照。分数背包按单位价值贪心最优因为物品可以切分单位价值排序天然对应连续的最优解结构。0-1 背包只要不能切分贪心立刻失效容量 10三件物品重量分别为 6、5、5价值分别为 6、5、5单位价值全为 1贪心先拿重量 6 的那件剩下 4 装不下任何东西总价值 6而最优解是拿后两件总价值 10。这个反例值得背下来它能在几秒钟内否掉一个“看起来很对”的方案。框架给的是判断顺序先试着证明贪心选择性质成功了就用贪心证不出来先构造反例反例找到了就退回动态规划。跳过证明直接实现是这类题目最常见的翻车方式。5. 常见问题与排查五个反复翻车的点5.1 概念理解上的两个偏差现象接口文档里写“该函数 O(n log n)”评审时被追问“平均还是最坏”答不上来最后发现排序是随机化版本最坏仍是 O(n²)。 原因把 O 当成了“最坏情况”的同义词。O 只描述上界与平均、最坏、期望是完全正交的概念随机化算法的上界甚至是一个随机变量。 解决文档里分三处写清楚——最坏 Θ(n²)、期望 Θ(n log n)、以及期望所依赖的随机化假设比如基准选取均匀随机。只要写了期望就必须写假设否则读者无法评估风险。现象遇到 T(n) 2T(n/2) n/lg n直接套主定理算成 Θ(n lg n)结果和实际对不上。 原因f(n) 与分水岭 n 之间只差一个对数因子没有情形一和三要求的那个 ε 级多项式间隔主定理根本不适用。 解决先用递归树把每层代价写出来求和再回头判断能不能用主定理。凡是 f(n) 里出现 lg n 且与分水岭同阶的都要警惕落在缝隙里。判定器代码里那个 eps 也就是为这种情况留的口子。5.2 实现层面的三个翻车点现象红黑树实现完成后随机插入一万个键没问题删除一百个之后查询速度明显变慢用可视化工具看有路径的黑节点数对不上。 原因删除时“兄弟为黑、两个侄子都为黑”这一支处理漏了。正确做法是把兄弟染红、额外黑色上推给父节点继续处理直到遇到红节点或到达根。漏掉这一支后被删路径的黑高少一红黑性质不再成立树逐渐退化。 解决写一个递归校验函数检查根为黑、红节点无红孩子、每条路径黑高一致这三条每次插入删除后都跑一遍配合随机操作序列跑几千轮把错误定位到第一次失败的操作上。现象用开放寻址实现哈希表删除时直接把槽位置空之后部分键再也查不到。 原因开放寻址的查找依赖探测链把槽位置空等于在链中间挖了个洞后续探测到空槽就认为键不存在直接返回未找到。 解决删除时写入墓碑标记DELETED查找时跳过墓碑但不停下插入时可以复用墓碑槽位装载因子统计要把墓碑计入否则表会被墓碑占满。另一条路是把整张表重建代价高但实现简单。现象动态规划版本在 n ≤ 10 时对拍全过n 30 时答案比暴力搜索小且随着 n 增大偏差越来越大。 原因状态维度不足把不同的历史过程压进了同一个状态看起来是“合并了等价情况”实际是丢掉了约束信息导致部分可行解被误判为不可行。 解决先写带完整参数的暴力递归把递归函数的所有参数列出来数一数缺哪个补哪个再用 n ≤ 12 的随机数据做穷举对拍。对拍不过就先怀疑状态定义而不是先怀疑转移方程。提示这五条里前两条是读书时就能避免的后三条只有在写代码时才会暴露。所以读完每一章之后最快的验证方式不是重读而是照着伪代码写一版能跑的实现再拿不变量去校验它。6. 复杂度边界与近似知道「算不动」之后该怎么设计教材最后几章讨论的东西初读时会觉得和工程无关多项式时间、多项式时间可验证、归约。但它给出的其实是一个决策框架。P 是能在多项式时间内求解的问题类NP 是给定一个候选解能在多项式时间内验证的问题类如果所有 NP 问题都能多项式归约到某个问题这个问题就是 NP 完全的。教材用一条完整的归约链把电路可满足性、3-CNF 可满足性、团、顶点覆盖、哈密顿回路、旅行商问题串在一起一旦其中任何一个被多项式解决整条链上的问题全部崩塌。这条链的工程意义不在于“证明某个问题很难”而在于告诉你什么时候应该停止寻找更快的精确算法。遇到 NP 完全问题可选的路径只有三条把问题放宽成近似版本把输入限制到有结构的特例上或者接受指数复杂度但用分支限界在小规模上跑。近似算法给出的是可证明的保证顶点覆盖的 2-近似只需取极大匹配的所有端点度量空间下的旅行商问题用最小生成树走两遍就是 2-近似集合覆盖按“覆盖未覆盖元素最多”贪心可证得约 ln n 倍的界。这些界比调参靠谱得多因为它们是数学结论不随数据分布漂移。代价也很明确2-近似意味着最坏情况下答案可能是最优解的两倍而某些问题在标准假设下不存在任意常数倍的近似。所以真正的设计动作是判断业务能容忍几倍误差再反推该用哪种近似而不是先挑算法再看效果。验证的方法我一般固定走三步小规模穷举对拍确认最优性构造退化输入空输入、全相同元素、已排序、哈希全冲突确认边界不崩把不变量写成断言跑长随机序列确认结构没有被悄悄破坏。这三步做完基本上不会留下隐蔽的错。从那以后我每次实现一个新结构或者写一个 DP都先把不变量和状态定义写成 assert 再写逻辑宁可前期麻烦一点也不想在半夜对着一个“结果偶尔偏小”的黑匣子找后悔药。这份原版教材值得放在手边反复翻的原因也正在于它把每条结论的成立条件都摊开写了——你能看到边界在哪也就能判断自己的场景是不是在边界内。希望帮到你。本文还有配套的精品资源点击获取
