简介《算法导论》第三版英文原版PDF面向计算机专业学生、考研备考者与算法工程师用于系统梳理数据结构与算法知识体系、夯实复杂度分析功底。资源包为单个PDF文件压缩后约5.12MB完整保留MIT Press原书排版与目录含34章正文与索引便于按章检索、对照课程阅读。内容从算法在计算中的角色、插入排序与分治入门讲起依次展开函数增长与渐近记号、概率分析与随机化算法再进入排序与顺序统计、堆、快速排序、线性时间排序以及哈希表、二叉搜索树、红黑树等数据结构后续覆盖图算法、动态规划、贪心与回溯、NP完全性等进阶主题并配有大量伪代码、定理证明与习题。已有640人学习适合作为课程教材、刷题与论文写作的参考底本。1. 伪代码比真代码更难读一本教材为什么敢不给你能跑的程序翻开这本《算法导论》英文原版教材第一反应往往是失望几百页里没有一行能直接编译运行的程序所有算法都写成一种混着数学符号、关键字和缩进的伪代码。这在今天这个连 README 都要塞个可执行示例的年代显得很反常。但这个选择恰恰是它的核心设计——伪代码把语言层面的噪音全部剥掉内存管理、类型转换、边界检查、库函数命名、异常处理一个都不留只剩算法的骨架。于是同一段分区逻辑你既能把它翻成 C 的指针搬运也能落成 Python 的切片。代价是读者必须自己在脑子里补上运行时语义而这个“补”的过程正是后面所有翻车和顿悟的来源。2. 渐近记号为什么 O 被用错得最多而 Θ 才是精确的那个2.1 从运行时间到增长量级被丢掉的常数项去哪了分析一个算法第一步不是数指令而是先约定一个计算模型。教材用的是随机访问机模型一条指令常数时间一次内存访问常数时间输入规模用 n 表示。在这个模型下插入排序的最坏情况代价是an² bn c归并排序是dn log n en f。这些系数取决于编译器、CPU 和缓存换台机器就变。真正稳定的是当 n 足够大时谁压倒谁所以分析的目标从一开始就不是“多少毫秒”而是“n 翻倍时代价怎么变”。丢掉低阶项和常数因子是为了让结论跟机器无关。这是一次典型的抽象取舍你换来的是可比较、可证明、跨平台的结论付出的是对小规模输入的失真。血泪经验是n 小于几十的时候一个带系数 200 的 O(n²) 算法经常打赢一个带系数 5000 的 O(n log n) 算法——因为常数项里藏着缓存命中率和分支预测。教材在讲归并排序时明确提过这个交叉点很多工程上的“优化”之所以翻车就是只看了量级没看常数。还有一层更隐蔽的东西分析对象是“输入规模”而不是“数据量”。图算法里规模是顶点数加边数矩阵算法里是阶数字符串匹配里是主串长度加模式串长度。规模定义错了后面的所有推导都白搭。用 E 表示边数、V 表示顶点数稀疏图上 O(E log V) 和稠密图上 O(V²) 是两个完全不同的世界把二者混为一谈是读图算法章节时最常见的理解偏差。2.2 Θ、O、Ω 的形式化它们是集合不是函数三种记号的定义都是集合。Θ(g(n)) 表示所有满足“存在正常数 c₁、c₂ 和 n₀使得当 n ≥ n₀ 时恒有 0 ≤ c₁·g(n) ≤ f(n) ≤ c₂·g(n)”的函数 f(n) 的集合。O 只保留上界那一半Ω 只保留下界那一半。写f(n) O(g(n))是一种约定俗成的滥用严格说是f(n) ∈ O(g(n))。理解了“集合”这一点就能看清最常见的误用说“快速排序是 O(n log n)”其实信息量很低因为 O 只给上界说它是 O(n³) 也成立。准确的说法是最坏情况 Θ(n²)、期望情况 Θ(n log n)。同理说“插入排序是 O(n²)”掩盖了它在近乎有序的输入上是 Θ(n) 这个事实——而这正是很多工程库在小数组上切回插入排序的理论依据。下面这段代码用来做一件事给定 f(n) 和 g(n)扫描一遍找出是否存在合法的 c₁、c₂、n₀从而验证 Θ 关系。def check_theta(f, g, c1, c2, n_start1, n_max5000): 验证是否存在 n0使得对所有 n n0 都有 c1*g(n) f(n) c2*g(n)。 f, g: 输入 n 返回数值的函数 c1, c2: 候选常数c1 对应下界c2 对应上界 n_start: 从哪个 n 开始找 n0 n_max: 搜索上界 返回: 合法的 n0找不到返回 None for n0 in range(n_start, n_max): if all(c1 * g(n) f(n) c2 * g(n) for n in range(n0, n_max)): return n0 return None f lambda n: 3 * n**2 2 * n 1 g lambda n: n**2 print(check_theta(f, g, 3, 4)) # 输出 3n3 时 3n^2 f(n) 4n^2 成立 print(check_theta(f, g, 1, 2)) # 输出 None下界取 1 太松、上界取 2 太紧永远不成立sweep的逻辑是n₀ 本身就是定义的一部分你不需要它等于 1。上例中3n² 2n 1 ≤ 4n²要成立需要n² ≥ 2n 1也就是 n ≥ 3所以 n₀ 3 合法。第二行返回 None 说明常数选错了即使关系客观成立也验证不出来——这正是很多人在作业里“算对了但证不出来”的原因。教材里还给了小 o 和小 ω分别表示“严格小于”和“严格大于”量级f(n) o(g(n))意味着对任意正常数 c 都存在 n₀ 使f(n) c·g(n)。它们看起来多余但在主定理的三种情况判定里是刚需——情况一要求f(n) O(n^(log_b a − ε))那个 ε 0 的存在性本质上就是小 o 的语言。2.3 递归式三件套代入法、递归树、主定理分治算法的代价天然写成递归式T(n) aT(n/b) f(n)是最常见的形式a 个子问题每个规模是原来的 1/b合并代价 f(n)。解它有三种手段对应三种不同的用途。代入法是证明不是求解。你先猜出答案再用数学归纳法验证常数成立。它的价值在于处理主定理覆盖不到的形式比如T(n) T(n/2) T(n/4) n这种两个不同缩小倍数的式子。递归树法是求解把递归展开成树每层代价加起来再对层数求和。主定理是查表直接给出三种情况的闭式解但要求 f(n) 满足正则条件a·f(n/b) ≤ c·f(n)某个 c 1这条条件挡掉的是那些合并代价在子问题里反而变大的病态情形。递归树最值得手推一遍因为它能直观回答“代价到底堆在哪一层”。下面这段代码把树逐层展开用归一化方式打印每层总代价def tree_levels(a, b, k, depth): 展开 T(n) a*T(n/b) n^k 的递归树。 a: 每层分裂出的子问题数 b: 规模缩小倍数 k: 合并代价 f(n)n^k 的指数 depth: 展开层数 输出每层的子问题数与归一化总代价以 n^k 为单位 for level in range(depth 1): nodes a ** level # 第 level 层子问题个数 per_node 1.0 / (b ** (k * level)) # 每个子问题的合并代价归一化到 n^k print(flevel{level:2d} nodes{nodes:8d} cost{nodes * per_node:9.4f} * n^{k}) # 归并排序a2, b2, f(n)nk1每层代价恒为 n tree_levels(2, 2, 1, 5) # 斯特拉森矩阵乘法a7, b2, f(n)n^2k2每层代价几何级递减叶子层主导 tree_levels(7, 2, 2, 4)第一组输出每层都是1.0 * n这就是主定理情况二每层代价相等总代价 层数 × 每层代价 Θ(n log n)。第二组输出从1.0一路掉到0.19说明合并代价随层数迅速缩水代价全部压在叶子层总代价由a^log_b n n^(log_2 7) ≈ n^2.81决定——这正是把 8 次乘法压到 7 次带来的收益指数从 3 降到 2.81。这三件工具的关系要记牢主定理负责快代入法负责严谨递归树负责给直觉。实际做题时的顺序通常是递归树先猜、代入法后证主定理用来交叉验证。跳过递归树直接背主定理的三种情况遇到带正则条件不满足的题就只能干瞪眼。3. 排序的下界不在算法里在“比较”这个动作里3.1 决策树模型Ω(n log n) 是谁规定的“比较排序至少需要 Ω(n log n) 次比较”这个结论经常被当成经验之谈实际上它是一条严格的下界定理而且适用范围比多数人以为的窄得多。证明用的是决策树模型把算法执行过程看成一张二叉树每个内部节点是一次a[i] a[j]的比较两条出边对应两种结果每个叶子对应一个可能的输出排列。n 个互异元素的排列有 n! 种所以决策树至少要有 n! 个叶子。高度为 h 的二叉树最多有 2^h 个叶子于是2^h ≥ n!即h ≥ log₂(n!)。用斯特林公式展开log₂(n!) n log₂ n − O(n)结论就是 Ω(n log n)。这里的关键前提是“信息只能通过比较获得”——每次比较返回一个比特要区分 n! 种可能光信息量就要求至少 log₂(n!) 个比特。这条下界约束的是比较模型不是排序问题本身。一旦你能从别处获得信息——比如知道元素是 0 到 k 的整数或者知道它们均匀分布在 [0,1) 上——下界就不再适用。这是理解线性时间排序的钥匙它们并没有违反定理只是绕出了定理的适用域。3.2 计数排序与基数排序用额外信息换掉比较计数排序的核心是三个循环统计频次、求前缀和、反向填充。第三步为什么必须反向是这段代码唯一的坑。def counting_sort(a, k): a: 待排序数组元素取值必须在 [0, k] 内 k: 值域上界 返回: 稳定排序后的新数组原数组不变 count [0] * (k 1) for x in a: count[x] 1 # 1. 频次统计 for i in range(1, k 1): count[i] count[i - 1] # 2. 前缀和count[v] 表示 v 的元素个数 out [0] * len(a) for x in reversed(a): # 3. 逆序遍历保证相等元素相对次序不变 count[x] - 1 out[count[x]] x return out参数k是值域上界不是数组长度这个区分很重要时间与空间都是 Θ(n k)当 k Θ(n) 时才是线性的如果 k 远大于 n比如排序 1000 个取值范围是 10⁹ 的整数这套做法会直接爆内存此时应该换基数排序或比较排序。第三步的reversed不是随手写的。若从前往后遍历count[x]递减后会把后面出现的相同元素放到前面稳定性立刻丢失。稳定性本身对计数排序没意义但基数排序靠它活着——基数排序把整数按位切成若干轮每一轮用一次稳定排序低位排完后的相对次序必须被高位排序保留否则前面所有轮次全白干。基数排序的代价是Θ(d(n k))d 是位数k 是每位的取值范围。选进制是个真实的工程权衡k 取 256 时 d 4 就能覆盖 32 位整数每轮一次线性扫描k 取 2 时 d 32虽然每轮空间极小但轮数暴涨。桶排序则是另一条路它假设输入均匀分布把 [0,1) 切成 n 个桶期望情况下每个桶常数个元素总代价 Θ(n)但一旦分布倾斜全部元素挤进一个桶就退化成桶内再排序的最坏情况 Θ(n²)。3.3 快速排序的随机化期望 O(n log n) 是怎么算出来的快速排序最坏 Θ(n²)、期望 Θ(n log n)关键是这个“期望”对什么取。教材给出的分析路径很漂亮随机化版本不随机选输入而是随机选枢轴于是对任意固定输入算法的行为等价于对输入做一次随机置换。期望是对算法内部的随机选择取的不是对输入分布取的——这一点决定了随机化快排没有“坏输入”只有坏运气。分析的核心是指示器随机变量。对排好序后的第 i 小和第 j 小元素i j它们被比较当且仅当在区间[i, j]中第一个被选为枢轴的元素是 i 或 j 本身概率是2/(j − i 1)。对所有元素对求和期望比较次数是ΣΣ 2/(j−i1) ≈ 2n ln n ≈ 1.39 n log₂ n。这个 1.39 的系数比归并排序的 1.0 大但快排的常数因子小、原地、缓存友好实际跑起来通常更快——又是一个量级相同、常数决定胜负的例子。固定枢轴永远取第一个元素的问题不是“平均慢”而是“存在大量真实存在的坏输入”。已排序或逆序的数组是最常见的两种此时每次分区只减少一个元素递归深度 n复杂度 Θ(n²)而且在递归实现下会直接栈溢出。三数取中能缓解但不能根治因为构造出三数取中失效的序列并不困难。import random def partition(a, lo, hi): Lomuto 分区返回枢轴最终位置 pa[lo..p-1] a[p] a[p1..hi] r random.randint(lo, hi) # 随机枢轴消除对输入顺序的依赖 a[r], a[hi] a[hi], a[r] pivot a[hi] i lo - 1 for j in range(lo, hi): if a[j] pivot: i 1 a[i], a[j] a[j], a[i] a[i 1], a[hi] a[hi], a[i 1] return i 1这段代码有两个容易被忽略的细节。第一random.randint(lo, hi)包含hi所以交换后枢轴在末尾分区的循环边界range(lo, hi)天然排除了枢轴本身。第二返回的i 1是枢轴的最终下标递归时必须写成[lo, p-1]和[p1, hi]——如果写成[lo, p]当分区结果恰好在端点时会无限递归。Hoare 分区版本返回的是“分界位置”而非枢轴位置两种写法的返回值语义完全不同混用是经典翻车点。工程上还会叠三层优化小区间通常 16 个元素以下切回插入排序减少递归开销三路分区处理大量重复元素把等于枢轴的元素一次性归位尾递归消除只对较小的一侧递归、较大的一侧用循环把最坏递归深度压到 O(log n)。这三条都不改变渐近复杂度但决定了实现在真实数据上能不能跑得过归并排序。4. 数据结构不变量才是本体操作只是维护它4.1 红黑树的五条性质为什么最长路径不超过最短路径的两倍红黑树常被当成“平衡二叉搜索树的一种”但它真正的设计是给每个节点加一个比特的颜色用五条约束把树高控制在 2log₂(n1) 以内。性质是每个节点非红即黑根是黑的每个叶节点哨兵 NIL是黑的红节点的两个子节点都是黑的从任一节点到其所有后代叶节点的简单路径上黑节点数目相同。前四条是语法第五条是真正的杠杆。定义黑高 bh(x) 为从 x 到叶子的路径上的黑节点数不含 x 自身第五条保证这个值唯一。由“红节点不相邻”可得任何一条从根到叶的路径上红节点数不超过黑节点数所以最长路径 ≤ 2·bh最短路径 ≥ bh两者比值不超过 2。于是树高被黑高锁死而黑高又受节点总数约束一棵黑高为 h 的树至少有 2^h − 1 个内部节点反解出 h ≤ 2log₂(n1)。整条推理链干净利落这也是为什么红黑树不做完美平衡却依然 O(log n)。所有插入删除操作本质上都是在改完结构之后用旋转和重新着色把第五条性质修回来。旋转是最小粒度的重排def left_rotate(tree, x): 对节点 x 做左旋x 的右孩子 y 上升接管 x 的位置。 前提x.right 不是哨兵 NIL。 y x.right x.right y.left # y 的左子树挂到 x 的右子树 if y.left is not tree.nil: y.left.parent x y.parent x.parent # y 接管 x 的父指针 if x.parent is tree.nil: 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左旋只改三组指针y 的左子树改挂到 x 右侧、y 接管 x 的父指针、x 成为 y 的左孩子。它保持中序遍历序列不变也就是说它不破坏二叉搜索树的有序性只调整形状。右旋完全对称。插入修正的三种情况叔叔节点为红、叔叔为黑且当前节点是内侧孩子、外侧孩子本质上是在把“红红相连”这个局部违规沿着树往上推每推两层做一次旋转总代价 O(log n)。删除比插入麻烦一个量级因为删掉一个黑节点会破坏第五条性质需要用“额外的一层黑色”这个概念在树上传递补偿四种情况里有两种需要旋转。教材在删除这一节的篇幅明显更长这不是编排失衡而是这个数据结构真实的复杂度分布——插入只是局部修补删除要维护全局黑高一致。4.2 势能法动态表扩容量摊还 O(1) 的账怎么算动态数组扩容这件事工程师的直觉是“偶尔复制一次平均下来还好”但“平均”是个含糊的词。摊还分析给的是严格结论一串操作的总额还代价上界。三种方法里势能法最适合回答“为什么是 3 而不是 2”。设表当前容量为 size已存元素数为 num定义势函数Φ 2·num − size。这个势函数在表刚好半满时为 0越满越大扩容瞬间会因为 size 翻倍而骤降——物理意义是“攒下的势能在扩容时被一次性释放抵消了复制成本”。第 i 次操作的摊还代价ĉᵢ cᵢ Φᵢ − Φᵢ₋₁。不扩容时插入一次实际代价 1num 加 1 使 Φ 增加 2摊还代价 3。扩容时num 从 size 变成 size1实际代价是 1 次插入加 size 次复制Φ 从2·size − size size变成2(size1) − 2size 2势能变化是2 − size摊还代价(size 1) (2 − size) 3。两种情形都是 3所以 n 次插入的总代价 ≤ 3n。关键在2·num − size这个系数如果用Φ num − size/2不扩容时摊还代价是 1 1 2扩容时是(size1) (1 − size/2)约为 size/2 1不构成常数上界。系数必须让势能在扩容前攒够 size才能一次性抵掉复制。这套账可以直接对应到现实里的 vector、ArrayList、切片扩容策略。很多实现的扩容倍率取 1.5 或 2原因不是玄学——倍率是常数时复制总次数才是几何级数摊还代价才是 O(1)如果每次只加固定长度总复制次数退化成 Θ(n²)。收缩侧也有坑如果扩容阈值和缩容阈值设得太近比如 100% 扩容、50% 缩容会在边界上反复抖动所以多数实现把缩容阈值压到 1/4。4.3 B 树为什么数据库索引不用红黑树到这里必须换一次模型。前面所有分析都建立在“一次内存访问常数时间”上而磁盘和 SSD 的现实是一次随机页读取比一次内存比较大几个数量级。这时候该优化的不是比较次数而是 I/O 次数。B 树把每个节点的键数上限设为2t − 1t 是最小度下限设为t − 1除根以外。这个上下界的设计意图很明确一个节点正好占一个磁盘页节点内的键一次性读进内存线性扫描几乎免费同时保证节点的孩子数在 t 到 2t 之间树高被压在log_t n。t 取 1000 时三层就能存下十亿级别的键查找最多三次磁盘 I/O。红黑树是二叉的树高是 2log₂ n同样规模下要走三十层每一层都是一次潜在随机 I/O。B 树的分裂和合并都发生在“节点溢出”时从叶子往上递归传播和红黑树的插入修正思路一致但触发条件是键数越界而不是颜色违规。教材把 B 树的删除单独列一节因为删除需要处理从兄弟节点借键、与兄弟合并、根节点收缩三种情况而合并又可能引发父节点溢出逻辑比插入长得多。这里有个常被忽略的取舍B 树的所有叶节点都在同一层这个性质保证了查找代价稳定但也意味着它不适合范围查询的局部性优化。B 树把数据全部推到叶子并用链表串起来正是为了弥补这一点——教材没有展开讲 B 树但从 B 树的定义推过去只有一步。5. 排查把伪代码翻成真代码时最容易翻车的五处5.1 下标与边界伪代码从 1 开始代码从 0 开始教材的数组下标统一从 1 开始这不是随意的因为堆的父子关系parent(i) ⌊i/2⌋、left(i) 2i、right(i) 2i1在 1-based 下形式最干净。一旦翻成 0-based这三个公式全部要重写。这不是难事难的是只改一半。现象堆排序在小数组上偶尔错位大数组上结果正常快速排序在特定输入下无限递归。原因堆的build_max_heap在 1-based 下从⌊n/2⌋开始下沉0-based 下最后一个非叶节点是⌊n/2⌋ − 1如果沿用n//2会从叶子节点开始调用max_heapify把一个叶子当成内部节点去访问它的孩子越界或者读到垃圾值。快排则是分区返回值语义混用Lomuto 返回枢轴位置递归要减一Hoare 返回分界点递归不减。解决所有从伪代码翻译的数组算法第一件事是把上下界写成变量lo, hi而不是硬编码然后在纸上用 n 1、2、3 三个规模跑一遍堆的构建起点统一写成n // 2 - 1快排的递归区间统一写成闭区间并配一个assert p lo and p hi。现象二分查找在数组只有两个元素时死循环。原因while lo hi配mid (lo hi) // 2和lo mid的组合当hi lo 1时 mid 恒等于 lo区间不收缩。解决把循环不变量写死在注释里——[lo, hi]闭区间内搜索时用while lo hi配lo mid 1 / hi mid - 1[lo, hi)半开区间时用while lo hi配hi mid。两套写法不能混混了就是无限循环或者漏查一个元素。5.2 状态标记浮点、墓碑与哨兵现象Dijkstra 在一部分图上结果偏大换一组数据又正常。原因松弛时用浮点数比较if dist[v] dist[u] w路径长度一旦涉及无法精确表示的小数dist[u] w和真实值之间的舍入误差会让本该成立的不等号失败或者让已经收敛的节点被反复更新。更隐蔽的一种是允许多次入队却没有做“过期检查”队列里堆积大量旧状态结果看着对但复杂度退化。解决权重是整数就全程用整数必须用浮点时加一个EPS 1e-9的容差并在弹出堆顶时检查if d dist[u]: continue跳过过期条目。现象开放寻址哈希表删除一个键之后原本能查到的另一个键突然查不到了。原因开放寻址的查找是沿探测序列前进、遇到空槽就停。删除时如果直接把槽位置空等于在探测链中间挖了个洞后面所有本该被找到的键全部失联。解决引入墓碑标记 DELETED查找遇到墓碑继续探测、遇到真正的空槽才停插入可以复用墓碑槽位。代价是墓碑会随着删除操作累积装载因子里必须把墓碑也算进去否则性能会缓慢劣化。这是典型的“删除比插入难”和红黑树删除、B 树删除是同一个道理。现象归并排序的合并阶段数组越界或者哨兵值被当成真实数据。原因教材用一个大于所有元素的哨兵∞放在两个子数组末尾省掉边界判断翻成代码时用了一个“足够大”的常数结果数据里真有更大的值。解决要么用真正的float(inf)要么老老实实写双指针加边界判断——后者代码长三行但不会在半年后因为数据范围变化而炸。哨兵是给伪代码提可读性用的不是给生产代码省事的。5.3 复杂度与常数别拿渐近结论当性能预算现象把一个 O(1) 的链表操作换成数组操作后整体反而变慢了。原因数组的中间插入是 O(n) 的搬移链表的插入确实是 O(1)但链表节点分散在堆上每次遍历都是一次缓存未命中数组是连续的顺序扫描的常数因子可能小一个数量级。教材的 RAM 模型假设所有内存访问等代价真实机器不是。解决n 小的时候按常数因子选结构n 大的时候先看访问模式是顺序还是随机再看渐近复杂度。这条不能反着来。现象图算法在稀疏图上跑得比预期慢很多。原因用了邻接矩阵存图找邻居要扫一整行复杂度从 O(V E) 退化成 O(V²)。解决先算一下 E 和 V² 的比值E 远小于 V² 时用邻接表稠密图或者需要 O(1) 判断两点是否相邻时用矩阵。教材在图的表示这一节把两者的适用边界讲得很清楚只是很多人直接跳过。现象递归实现的快排在十万级数据上栈溢出。原因固定枢轴 已排序输入递归深度等于 n。解决随机化枢轴只能把期望深度降到 O(log n)不能消除最坏情况真正的解法是尾递归消除——每层只对较短的一侧递归较长的一侧用循环处理最坏递归深度被压到 O(log n)。这条在语言没有尾调用优化时尤其重要。6. NP 完全性证不出多项式算法为什么反而是有用的结论很多人读到 NP 完全性这一章会觉得泄气花了几十页证明一个问题难结论却是“没有高效算法”。但换个角度看这是整本书里信息密度最高的结论之一——它让你在动手之前就知道该放弃什么。一个归约证明节省的是几周的无效尝试这比任何一个具体算法都值钱。判定表放在这里是因为归约方向搞反是这一章最高频的错误类别判定特征典型问题工程含义P存在多项式时间确定性算法排序、单源最短路、最大流直接求精确解NP给定解可在多项式时间验证布尔可满足性、哈密顿回路猜解容易找解不一定NP 完全属于 NP且所有 NP 问题都可归约到它顶点覆盖、集合覆盖、旅行商判定版精确解基本无望转向近似或特例NP 难不要求属于 NP但 NP 完全问题可归约到它旅行商优化版、停机问题连验证都不保证快证一个问题是 NP 完全两步先证它属于 NP给一个解能在多项式时间验证再把一个已知的 NP 完全问题 Y 归约到它Y ≤ₚ X。方向不能反——把 X 归约到 Y 只能说明 X 不比 Y 难什么也没证明。这一章的所有习题都在练这一个动作练的不是数学技巧是思维方向。知道问题难之后出路有三条教材最后一章给的正是这三条。第一条是近似顶点覆盖有一个简单的 2-近似——反复取一条未覆盖的边把两个端点都放进解集每条被选的边至少有一个端点不在最优解里所以解集大小不超过最优解的两倍。集合覆盖则用贪心拿到 ln n 倍的近似而且这个界在一般假设下已经是最优的。第二条是限制结构旅行商问题在一般图上没有常数因子近似除非 P NP但如果距离满足三角不等式用最小生成树走一圈再短路掉重复点就是 2-近似把最小生成树换成最小权完美匹配可以做到 1.5-近似。第三条是接受指数n 只有二十几的时候状态压缩 DP 的 O(2ⁿ·n²) 完全够用比起折腾近似解精确解更省心。我自己的习惯是拿到一个新问题先在纸上判断它像不像 NP 完全——如果它天然带“选一个子集满足某些约束”或者“找一条经过所有点恰好一次的路”的形状就先假定它难去找已知的归约对象同时开始想近似方案和特例条件。这个判断花不了十分钟但能省掉后面几周的弯路。从那以后我每次设计涉及组合选择的模块都会在文档第一行写清“这个问题属于哪一类、我们用的是近似还是特例”后面接手的人至少不会重复踩同一个坑。希望帮到你。本文还有配套的精品资源点击获取
