简介《The Probabilistic Method》第三版英文原版PDF面向数学与计算机科学方向的研究生、教师及科研人员系统讲解如何借助概率论工具证明组合对象的存在性并分析随机算法适合组合数学、图论、理论计算机与复杂性理论等方向的学习者。全书以随机化证明为主线覆盖二项式系数与组合恒等式、大数定律与中心极限定理、Ramsey数与边色数等图论结论、纠错码与信息论、算法平均情况分析、零一法律及Lovász局部引理并配有较丰富的例子说明定理的使用条件阅读前需具备概率论、图论和线性代数基础。资源包仅含1个PDF文件大小约7.77MB便于在电脑或平板上查阅与检索。目前已有150人学习适合作为课程补充读物或研究时的工具书帮助读者建立概率方法的证明思路并迁移到自身课题中。1. 一本把「存在性」变成可计算问题的书卡在「要证明存在一个满足某组约束的组合结构但构造不出来、枚举又是指数级」这种局面上是很多人第一次认真翻《The Probabilistic Method》第三版的真实动机。这本书讲的不是概率论入门而是一整套把存在性命题改写成概率陈述的工具箱不构造具体对象而是在一个精心设计的概率空间里随机取一个对象证明它满足全部约束的概率严格大于零。适合两类人写论文需要给出非构造性下界的研究生以及做随机算法、图算法、编码设计时需要一个「能不能行」的判据的工程师。第三版在原有方法篇之外补了随机图相变、图性质测试和去随机化方法篇仍是主干。2. 期望、改变与二阶矩三种存在性证明怎么分工三种工具看起来都在算概率实际解决的问题完全不一样。期望法回答「有没有」改变法回答「坏结构太多怎么办」二阶矩回答「除了存在是不是还很常见」。选错工具的典型症状是明明用期望法已经推出 E[X]1却还在死磕 P(X0) 的精确表达式或者明明坏结构之间存在强相关却拿并集界硬算最后界差出好几个数量级。这一章按「能算什么 → 为什么能算 → 参数怎么定 → 什么时候失效」的顺序把三种工具拆开。2.1 基本方法的三段式概率空间、坏事件、正概率基本方法的流程固定得像模板先定义随机对象再定义「坏事件」——对象不满足目标性质这件事最后证明坏事件的概率严格小于 1。以两色完全图的临界数 R(k,k) 为例随机给 K_n 的每条边独立地染红或蓝一共 2^{C(n,2)} 种等概率染色。坏事件是「存在一个 k 点全红团或者全蓝团」用并集界处理P(坏) ≤ C(n,k) · 2 · 2^{-C(k,2)} C(n,k) · 2^{1-C(k,2)}只要这个上界严格小于 1就存在一种染色既没有红 K_k 也没有蓝 K_k于是 R(k,k) n。这里有个容易被忽略的点并集界丢掉了坏事件之间的全部重叠信息算出来的上界是保守的但这恰好是它好用的原因——不需要知道任意两个单色团是否共存也不需要处理它们之间的相关性。代价是界偏松对 k 稍大一点能推出来的 n 就明显低于真实值。把这一步落成可跑的东西关键不是算 C(n,k)而是防止浮点溢出。C(200,50) 这种量级直接算会炸转到对数域就没问题from math import comb, log2 def max_n_for_k(k, n_max400): 返回满足 C(n,k)*2^(1-C(k,2)) 1 的最大 n即 R(k,k) n 的保证范围 best 0 for n in range(k, n_max 1): # 全部转到以 2 为底的对数域避免 C(n,k) 溢出 log2_bound log2(comb(n, k)) 1 - comb(k, 2) if log2_bound 0: # 等价于原不等式严格小于 1 best n else: break # C(n,k) 关于 n 单调增后面只会更差 return best for k in range(4, 11): print(k, max_n_for_k(k))这段代码有两个参数值得改n_max决定搜索上限k 大时要往上调break依赖 C(n,k) 对 n 的单调性改成不做 break 而是继续扫也不会改变结果只是多跑几轮。逻辑上还有一个隐含假设comb(n,k)在 nk 时返回 0所以起点必须从k开始否则log2(0)会直接抛异常。跑出来的数字不用和真实临界值比能稳定复现「k10 时保证 n 至少到某个值」这个结论就够了剩下的差距是并集界的固有损耗不是代码写错了。2.2 期望法为什么算 E[X] 比算 P(X0) 便宜并集界只回答「坏事件一个都不发生」的概率上界而期望法把问题改写成计数设 X 是坏结构的个数X 是随机变量E[X] 是它的平均值。如果 E[X] 1那么必然存在一个实例使 X 0——否则每个实例至少有一个坏结构X ≥ 1 处处成立平均值就不可能低于 1。这个论证只有一行但它绕开了「坏事件之间是否独立」这个通常算不动的核心难点因为期望的线性性不需要任何独立性假设。实际用的时候E[X] 通常写成「坏结构总数 × 单个坏结构出现的概率」。以超图的可二染色问题为例如果每个坏结构是一个最小不可二染色子图单个出现的概率是 2^{-s}s 是它的边数总数是 m那么 E[X] m·2^{-s}。条件 m 2^s 就保证了存在一种二染色让所有坏结构都被破坏。这套做法的失效信号很明确当 E[X] 算出来是 0.98 这种贴着 1 的值时结论仍然成立但毫无余量任何一点上界估计的粗糙都可能把结论吃掉。另一个更隐蔽的失效是「E[X] 1 但 X 的取值不是非负整数」——如果 X 被定义成某种加权和平均值小于 1 并不能推出存在 X 0 的实例这时候要么改成计数型随机变量要么改用别的工具。2.3 改变法删掉坏结构比修好它更划算有一类问题里 E[X] 大得离谱期望法直接失效但结构本身「很接近正确」随机取一个对象它只有少数几个局部缺陷删掉涉及缺陷的那几个元素就能得到合法的子结构。改变法的标准动作是随机生成 → 计算每个元素平均卷入多少个坏结构 → 删掉所有卷入坏结构的元素 → 估计剩下多少。模板大致是这样设共有 m 个坏结构每个坏结构涉及至多 b 个元素总元素数是 n。随机选出的对象里坏结构个数的期望是 E[X]那么平均每个元素卷入的坏结构数是 E[X]·b/n这里用「涉及」而不是「包含」是因为一个坏结构可能重复计入多个元素取上界即可。删掉所有卷入坏结构的元素之后坏结构一定全没了剩下的元素个数至少是 n 减去被删掉的个数。而被删掉的元素个数不超过 E[X]·b所以剩下的规模至少是 n - E[X]·b。这套推导的价值在于它给出的不是「存在一个」而是「存在一个规模至少多大的」。独立性数的下界、某些打包问题的下界都是这么来的。参数上唯一要小心的是 b 的取法b 取的是单个坏结构涉及的元素数上限取大了结论变弱但不会错取小了结论直接崩。经验做法是先用精确的涉及数算一遍再故意用宽松的 b 算一遍如果两次结论差距超过一个数量级说明 b 的估计有问题应该回去重新数。2.4 二阶矩方差告诉你「不只是存在」期望法证明的是「至少有一个」但很多场景需要更强的东西这个性质是不是普遍成立典型对象是不是都满足这时候看方差。设 X 是非负整数值随机变量那么P(X 0) ≤ Var[X] / E[X]²推导只用了一步切比雪夫型的不等式X 0 蕴含 |X - E[X]| E[X]于是 P(X0) ≤ P(|X-E[X]| ≥ E[X]) ≤ Var[X]/E[X]²。只要方差比期望的平方小一个量级X 0 的概率就被压得很低性质就不是「碰巧存在」而是「绝大多数对象都满足」。方差的计算是这条路上最容易翻车的地方。Var[X] Σ Var[X_i] Σ_{i≠j} Cov(X_i, X_j)初学者最常见的错误是只算第一项也就是把所有坏结构当成互相独立。当坏结构共享元素时协方差项可能是同阶甚至主导的。判断要不要算协方差项有个便宜的办法先只算 Σ Var[X_i]如果这个值已经远小于 E[X]²那协方差项再大也不太可能翻盘如果两者同阶就必须老老实实把相关项拆开通常按「共享一个元素」「共享两个元素」分类求和。2.5 三者的选择表与参数怎么定选工具不用凭感觉看三个信号坏结构数量是否可控、坏结构之间是否强相关、结论需要「存在」还是「普遍」。工具核心条件输出强度典型失效信号基本方法 并集界坏事件概率之和 1存在性坏事件数量多界远大于 1期望法E[X] 1存在性可带规模信息E[X] 贴着 1无余量改变法坏结构可被少量元素覆盖存在性 规模下界b 的估计过小结论虚高二阶矩Var[X] ≪ E[X]²普遍性 / 概率上界忽略协方差项局部引理每个坏事件只与少数事件相关存在性可算法化依赖图少画边参数定法上有个通用习惯先把所有不等式写成「左边是待估计量、右边是显式表达式」的形式把常数全部保留最后一步再代入具体数值。中途做近似比如把 (1-1/n)^n 当成 e^{-1}会让最终结论的适用范围模糊掉——书里大量结论是渐近的落地时必须反解出「n 至少多大才成立」这个反解过程里任何一个提前近似都会让门槛失真。3. 局部引理依赖图少画一条边结论就废了并集界要求坏事件概率之和小于 1一旦坏事件数量上千这个条件就基本不可能满足。局部引理换了个角度不要求和小于 1只要求每个坏事件「只和少数几个坏事件相关」且单个概率足够小。它把全局条件拆成局部条件是这本书里实用价值最高、同时也最容易被误用的一节。3.1 依赖图不是「相关图」边怎么画才算安全依赖图的定义很严格把每个坏事件画成一个顶点如果两个坏事件涉及同一组随机变量就在它们之间连边。注意这里是「涉及同一组变量」不是「统计上相关」。很多事件在统计上高度相关但变量集合不相交按定义它们之间没有边反过来两个事件变量集合相交即使实际相关性很弱也必须连边。这个定义方向决定了依赖图只能往多了画不能往少了画。少画一条边的后果不是界变松而是结论直接错——局部引理的证明依赖「给定一个事件的全部邻居之后它和其余事件条件独立」这条性质一旦被破坏整个归纳就塌了。实际排查时有个保守做法先按变量集合严格连边算一遍 d再人为把 d 放大一倍算一遍。如果两次结论方向一致说明你对依赖结构的理解没问题如果放大一倍之后条件就不满足了说明原来的余量本来就很薄实际落地时要格外小心。3.2 对称版与一般版的参数换算对称版的条件最好记设每个坏事件的概率不超过 p依赖图中每个顶点的度不超过 d如果e · p · (d 1) ≤ 1那么所有坏事件同时不发生的概率严格为正。这个式子里的 e 是自然常数不是误差项很多人第一次用时会把 (d1) 写成 d边界就偏了。为什么是 d1 而不是 d归纳过程中需要把「自己」也算进去写成 d 会得到一个略强的错误条件。一般版放弃了对所有事件用同一个上界改成给每个事件配一个权 x_i ∈ (0,1)条件是P(A_i) ≤ x_i · Π_{j ∈ Γ(i)} (1 - x_j)对称版是它的特例所有 x_i 取同一个值 1/(d1)。一般版的价值在于处理「概率不均匀」的场景少数几个事件概率特别大、其余都很小对称版会被那几个大的拖死一般版可以给大的配大权、小的配小权条件宽松不少。版本输入条件适用场景对称版统一上界 p、最大度 de·p·(d1) ≤ 1事件同质快速判断可行性一般版每个事件的 p_i 与权 x_ip_i ≤ x_i·Π(1-x_j)概率分布不均需要榨余量算法化版更强的概率条件重采样收敛需要真的构造出对象3.3 算法化版本从「存在」到「能跑出来」的代价局部引理的原版是非构造性的它告诉你「存在一个所有坏事件都不发生的赋值」但没告诉你怎么找。算法化版本补上了这一步做法是重采样随便给一个初始赋值找到当前被违反的坏事件只对它的变量集合重新随机赋值重复直到没有坏事件为止。只要每个坏事件涉及的变量数有上界、且概率条件比存在性版本更强一些这个过程期望意义下收敛。代价体现在两个方面。一是条件收紧存在性版本要求 e·p·(d1) ≤ 1算法版本在变量数较大时往往需要 p 再小一个量级实操中经常出现「书上的定理说存在但算法跑不出来」的情况不是算法实现错了是条件没到。二是每轮重采样的范围只重置被违反事件涉及的变量还是重置它的整个邻域收敛速度差别很大。工程上我一般先按最小范围重采样跑固定轮数不收敛再扩大到邻域扩大到邻域仍不收敛就回头检查 p 和 d 的估计。3.4 用一段脚本校验你的 p 和 d 是否达标局部引理的参数校验适合写成脚本因为手算 e·p·(d1) 很容易在量级上出错。下面这段同时做对称版判定和一般版的数值求解import math def symmetric_ok(p, d): 对称版e * p * (d 1) 1 时全部坏事件同时不发生的概率为正 return math.e * p * (d 1) 1.0, math.e * p * (d 1) def general_ok(probs, neighbors, iters500): 一般版迭代求最小可行权 x_i返回 (是否可行, 权向量) neighbors[i] 是事件 i 在依赖图中的邻居下标列表 n len(probs) x [0.1] * n # 初始权取小一点保证单调上升 for _ in range(iters): new_x [] for i in range(n): prod 1.0 for j in neighbors[i]: prod * (1.0 - x[j]) # 解 x_i * prod p_i 的最小可行 x_i并夹到 (0,1) xi probs[i] / prod if prod 1e-12 else 1.0 new_x.append(min(0.999, max(xi, 1e-9))) if max(abs(a - b) for a, b in zip(new_x, x)) 1e-9: x new_x break x new_x # 回代校验留 1e-12 容差抵掉浮点误差 ok all(probs[i] x[i] * math.prod(1 - x[j] for j in neighbors[i]) 1e-12 for i in range(n)) return ok, x # 例8 个坏事件每个概率 1e-3依赖图是一个 3-正则图 probs [1e-3] * 8 neighbors [[(i - 1) % 8, (i 1) % 8, (i 3) % 8] for i in range(8)] print(symmetric_ok(1e-3, 3)) print(general_ok(probs, neighbors))symmetric_ok返回布尔值和实际算出来的乘积第二项特别有用0.98 和 0.02 都判定为可行但余量完全不同后者说明结论很稳前者说明参数一动就崩。general_ok的迭代逻辑是求最小不动点初始权取 0.1 是为了让迭代从下往上收敛如果初值取 0.9迭代可能在可行域里来回震荡。iters是兜底轮数正常规模几十轮就收敛跑到 500 轮还没收敛基本可以判定不可行。这个脚本只做数值校验不构成证明——它给出的是「按这组参数一般版的条件看起来满足」最终结论仍要回到定理的严格形式。4. 集中不等式与泊松范式把「存在」推到「几乎必然」前面三章解决的都是「存在」但工程上更常问的是「这个量会不会偏离期望太远」和「一堆事件里一个都不发生的概率有多大」。这两个问题分别对应鞅集中和泊松范式前者管单个随机变量的尾部后者管大量弱相关事件的联合稀疏性。4.1 有界差分的鞅不等式什么时候集中是免费的设 Y f(X_1, ..., X_n)X_i 相互独立且改变任意一个 X_i 时 Y 的变化量不超过 c_i那么P(|Y - E[Y]| ≥ t) ≤ 2·exp(-2t² / Σ c_i²)这个不等式的好处是几乎不需要知道 Y 的分布只要变化量有界就能用。判断能不能用的标准很简单把 f 写成对每个坐标的依赖逐个估计「换掉一个坐标最多影响多少」如果这个影响不随 n 增长集中就是免费的如果某个坐标的影响随 n 线性增长比如 f 是最大值函数换一个坐标可能让最大值从 1 跳到 n这个不等式就什么都给不出。实际估计 c_i 时的常见错误是按平均影响算正确做法是按最坏影响算。举一个排序相关的例子Y 是某个统计量改变一个输入可能让整个排序结构重排这时最坏影响远大于平均影响用平均影响估 c_i 会得到一个过于乐观的界。经验做法是先找「最敏感的那个坐标」单独估它的 c其余取一个宽松上界这样得到的 Σc_i² 虽然偏大但结论是可靠的。4.2 联合事件不等式μ 和 Δ 两个量的用法设有一族坏事件 A_1, ..., A_mμ Σ P(A_i)Δ Σ_{i~j} P(A_i ∧ A_j)i~j 指两个事件在依赖图里相邻则P(一个坏事件都不发生) ≤ exp(-μ Δ)μ 是「期望发生多少个」Δ 是对两两同时发生的修正。当 Δ 远小于 μ 时不等式退化成泊松形式坏事件的数量近似服从泊松分布当 Δ 和 μ 同阶时修正项吃掉大部分余量界变得很松这时候说明事件之间的相关太强泊松范式不适用。用这个不等式之前要先想清楚两件事事件族是不是足够稀疏μ 不能大到每个位置都出事以及相关性是不是局部化的强相关只发生在近邻之间。两条都满足结论通常很好用有一条不满足要么换工具要么把事件族重新切分让它变稀疏。4.3 随机图相变临界窗口为什么难讲清楚随机图 G(n, p) 里 p c/n 是分水岭。c 1 时最大连通块只有 O(log n)c 1 时突然冒出一个 Θ(n) 规模的巨片。这条结论的证明思路是分支过程从一个顶点出发做广度优先搜索它在每一层「生出」的新顶点数近似服从参数为 c 的泊松分布泊松分布均值小于 1 时分支过程必然灭绝大于 1 时有正概率存活。难讲清楚的是临界窗口。p 1/n λn^{-2/3} 这个尺度上最大连通块的大小是 n^{2/3} 量级三种形态次临界、临界、超临界在这里交界直接用分支过程近似会失效因为不同分支之间的碰撞不能忽略。工程上如果只是做参数选型避开这个窗口就行要么让 c 明显小于 1要么让 c 明显大于 1.5落在窗口里讨论「到底有没有巨片」意义不大。4.4 数值验证用并查集把巨片位置跑出来相变的结论可以用几十行代码验证不依赖任何图论库。用并查集维护连通块逐条边做合并最后取最大块的大小import random def giant_ratio(n, c, trials5): 经验估计 G(n, c/n) 中最大连通块占顶点数的比例 total 0.0 for _ in range(trials): parent list(range(n)) size [1] * n def find(a): while parent[a] ! a: parent[a] parent[parent[a]] # 路径压缩 a parent[a] return a p c / n for i in range(n): for j in range(i 1, n): if random.random() p: ri, rj find(i), find(j) if ri ! rj: # 按大小合并控制树高 if size[ri] size[rj]: ri, rj rj, ri parent[rj] ri size[ri] size[rj] total max(size) return total / trials / n for c in (0.5, 0.8, 0.99, 1.5, 3.0): print(c, round(giant_ratio(1200, c), 4))参数说明n控制在几千以内因为边枚举是 O(n²)n1200 单次约 72 万次抽样五次跑下来几秒钟n 上到 5000 就明显慢了需要改成按几何分布跳采样。trials取 5 是权衡方差和耗时c 接近 1 时方差大要取到 20 以上才稳。c是平均度也是这条曲线的唯一控制参数。跑出来的比值在 c0.5 和 c0.8 时应该很小低于 0.02c1.5 和 c3.0 时应该跳到 0.5 以上——这个跳变的位置就是相变点和理论值 1 对得上误差来自有限 n 和临界窗口的宽度。5. 避坑读这本证明书最容易翻车的五个地方这本书的证明平均长度不到两页但每一步省略的推导都可能让人卡半天。下面五个坑是我自己反复踩、也见过别人反复踩的按「现象 → 原因 → 解决」写清楚。5.1 坑一证明看懂了实例还是拿不出来现象是定理读完觉得没问题回头想写代码验证发现根本不知道从哪下手因为证明从头到尾没给过任何构造步骤。原因在于这类证明的性质它只说明「满足条件的对象构成的空间非空」路径是「假设全都不满足推出矛盾」。矛盾推出来就结束了构造过程从来没有出现在证明里。改变法稍微好一点因为它至少给出了「删掉哪些元素」这个动作但删完之后剩下的结构长什么样证明并不关心。解决办法是分清「存在性结论」和「可构造结论」要在读的时候标记出来。如果只需要一个下界或者一个反例存在性非构造性证明够用如果要真的跑出实例就得去找算法化版本或者退一步用随机化搜索按证明里的概率分布随机采样检查是否满足性质重复到命中为止。后者在参数有余量时通常几百次内就能命中余量很薄时会直接卡死卡死本身就是个信号——说明这个参数点落在理论界的边缘实际不可用。5.2 坑二依赖图少画了边局部引理给出错误结论现象是按自己画的依赖图算出 d5、p0.01e·p·(d1) ≈ 0.16 远小于 1结论应该很稳但拿具体例子一测就发现反例。原因是依赖图漏了隐式依赖。最常见的情况是事件之间通过一个全局约束耦合比如所有事件都依赖「总和不超过某个值」这个条件变量集合两两不交但给定其他事件之后剩余事件的概率分布会变。按变量集合连边这种情况一条边都不画可实际上它们强相关。解决办法是改用更保守的连边规则只要两个事件的概率在给定对方之后发生变化就认为它们相邻。判断方法是手算一两个 P(A_i | A_j) 和 P(A_i) 对比差得明显就连边。这个规则会把依赖图变密、条件变严但结论不会错。另一个办法是先按严格规则算一遍再把 d 乘 2 重算两次都通过才放心用。5.3 坑三并集界用过头界和真实值差好几个数量级现象是坏事件只有十几个套并集界算出来概率上界是 3.7完全没信息量但直觉上这些事件同时发生的可能性很小。原因是并集界完全不管事件之间的重叠。当坏事件高度重叠比如都涉及同一批高频元素时ΣP(A_i) 会把同一块概率重复计入很多次上界虚高得离谱。事件越相关并集界越没用。解决办法是先看事件之间是否近似互斥或强相关如果是改用联合事件不等式用 Δ 修正重叠部分如果事件之间近似独立直接用乘积形式 P(∩¬A_i) ≈ Π(1-P(A_i)) 会比并集界强得多虽然这不再是严格上界但配合局部引理可以恢复严格性。判断该用哪个算一下 μ 和 Δ 的比值Δ/μ 小于 0.1 就用泊松形式大于 0.5 就说明重叠严重得换思路。5.4 坑四渐近结论直接套小规模数据现象是书上的定理写「对充分大的 n 成立」直接拿 n50 去用结果和定理说的完全相反。原因是渐近结论里的「充分大」是个未定常数证明过程中通常做了好几处「n 大于某个常数时成立」的放缩这些常数从没被显式算出来过。有些定理的证明里 o(1) 项在 n10⁶ 时才降到 0.01 以下n50 时它比主项还大。解决办法是把证明里的每一次放缩反解成显式不等式。具体做法是跟着证明走一遍把每一处「对充分大的 nA(n) ≤ B(n)」都写成 A(n) ≤ B(n) 的具体条件最后取所有条件的交集。这个过程很烦但反解出来的 n 门槛往往和直觉差好几个数量级。如果反解成本太高退而求其次做数值实验从小到大扫 n看结论从哪个 n 开始稳定成立把这个 n 乘 10 当作安全门槛用。5.5 坑五二阶矩里把相关事件当独立算方差现象是方差算出来比期望的平方小两个数量级结论漂亮得不像话但构造反例一搜就有。原因是只算了 Σ Var[X_i]漏了所有协方差项。当坏结构之间频繁共享元素时协方差项是正的且数量级和方差项相当漏掉它会把方差低估一个量级进而把 P(X0) 的界压得虚低。解决办法是把相关结构分类展开。按「共享 0 个、1 个、2 个元素」把所有事件对分组前一组近似独立可以不算后两组逐项算 Cov 并求和。如果分组太细算不动用联合事件不等式兜底它给出的界比精确方差松但不会因为你漏项而给出错误结论。判断要不要展开的标准是先只算对角项如果结论已经足够强比如 P(X0) 0.01对角项就够了如果算出来是 0.3 这种尴尬值说明对角项不够必须展开。6. 把书上的存在性证明落成脚本三步验证与阅读顺序表书读完之后真正留在手上的不是定理陈述而是一套「拿到一个新问题怎么下手」的流程。我自己固定走三步第一步把目标性质写成坏事件集合明确每个坏事件涉及的随机变量第二步用最粗的工具并集界或期望法先算一遍看条件离满足差多远第三步按差距大小选精化方向——差一个数量级以内上二阶矩或局部引理差好几个数量级说明概率空间选错了要换随机模型重来。这三步里第二步最容易跳过很多人一上来就用局部引理结果参数算到一半发现并集界其实就够了白折腾。阅读顺序上如果目标是把工具用起来方法篇的第 1、2、3、4、5、7 章按顺序读第 6 章相关性不等式和第 8 章泊松范式可以按需插入如果目标是做随机图或者算法分析第 9 章之后按主题挑第 11 章的相变、第 16 章的去随机化、第 17 章的图性质测试是第三版新增的三块和工程距离最近。每章末尾的习题里带星号的难度明显更高时间紧就先跳过不影响主线。附录里的大偏差界那张表建议单独复印一份放手边参数估计时经常要回头查。目标必读章可跳过建议配套动作快速判断存在性1、2、36、8并集界 期望法算一遍处理强相关事件5、6、812、13画保守依赖图跑参数校验脚本随机图与相变9、10、1114、15并查集模拟巨片位置算法可实现性16、1713重采样实现 收敛轮数统计最后说个血泪教训我早期读这类书习惯只看定理陈述和结论证明跳过觉得「知道有这么个工具就行」。结果真到用的时候参数怎么定、边界在哪、什么时候失效一条都答不上来只能从头再读一遍。现在我每次读到一个准备用的定理都会强制自己把证明里的每一处放缩反解成一个显式不等式写进一个单独的笔记文件用的时候直接查门槛。这个习惯救过我好几次——有一次算出来的 n 门槛比我原计划的数据规模大两个数量级提前发现省了一周的返工。希望帮到你。本文还有配套的精品资源点击获取
