第 09 册 算法与数据结构 · 本册导读
本册以 Cormen、Leiserson、Rivest、Stein《Introduction to Algorithms》第 3 版为底本，用 31 个章节文件和 1 个附录覆盖原书全部 35 章和附录 A–D。它回答量化研究和交易系统里一个绕不开的问题：同一个计算，怎样做才既对又快，规模放大十倍、一百倍以后还撑不撑得住。每章在原书主线之外都加了「量化实战」，用 Python 把算法落到因子计算、订单簿、组合构建、套利检测和回测工程上。
1. 本册定位
1.1 底本
| 项目 | 内容 |
|---|---|
| 书名 | Introduction to Algorithms（第 3 版，常称 CLRS） |
| 作者 | Thomas H. Cormen、Charles E. Leiserson、Ronald L. Rivest、Clifford Stein |
| 出版 | MIT Press，2009 |
| PDF 页数 | 1,313 页 |
| 页码换算 | 原书页码 = PDF 页码 − 21（正文第 1 页在 PDF p.22） |
| 原书结构 | 八个部分：I 基础（第 1–5 章）、II 排序与顺序统计量（6–9）、III 数据结构（10–14）、IV 高级设计与分析技术（15–17）、V 高级数据结构（18–21）、VI 图算法（22–26）、VII 算法问题选编（27–35）、VIII 附录（A–D） |
各章末尾的「原书对照」表一律给 PDF 页码；第 24–29 章另在括号里给出原书页码。查原书时按 PDF 页码翻最快。
原书是算法领域的标准教材，特点是伪代码统一、每个算法都配正确性证明和运行时间分析、习题和思考题极多。本册保留了原书的定理、引理、习题和思考题编号（例如「定理 24.6」「习题 15.3-5」「思考题 26-3」都来自原书），便于对照原书做题；章内小节编号按教学顺序重排，可能与原书小节号不同，例如本册 15.2 节「钢条切割」对应原书 15.1 节，以「原书对照」表为准。
1.2 本册结构：合并与拆分
为了让篇幅与量化用途相称，部分原书章节做了合并或拆分。文件编号不连续是有意的：编号取自原书章号，缺的号码已并入前一个文件。
| 原书章 | 本册文件 | 处理方式 |
|---|---|---|
| 第 1、2 章 | 01 | 合并：算法的作用 + 插入排序、归并排序、循环不变式 |
| 第 4 章 | 04a、04b | 拆分：04a 讲 4.1–4.2 的两个分治算法；04b 讲 4.3–4.6 的递归式求解与主定理 |
| 第 12、13 章 | 12 | 合并：二叉搜索树 + 红黑树 |
| 第 15 章 | 15a、15b | 拆分：15a 按原书讲方法与四个经典问题；15b 是本册新增的量化建模篇，依托原书思考题 15-1、15-7、15-10、15-11 |
| 第 18、19、20 章 | 18 | 合并：B 树、斐波那契堆、van Emde Boas 树，以用途和复杂度为主 |
| 第 31、32、33 章 | 31 | 合并：数论、字符串匹配、计算几何三部分 |
| 附录 A–D | A | 合并为一篇速查：求和、集合与图、计数与概率、矩阵 |
因此本册没有第 02、13、19、20、32、33 章文件。正文中提到「原书第 13 章」「原书第 33 章」时，分别到第 12 章、第 31 章第三部分去找。
1.3 在量化交易中的作用
量化工作里，算法问题通常不是以「请实现红黑树」的面目出现的，而是藏在下面这些日常任务里：
- 估算成本，找瓶颈。 因子流程从 500 只股票扩到 5000 只，哪一步会先崩？渐近记号和递归式让你在写代码之前就能回答（第 01、03、04b 章）。协方差求逆是 \(O(N^3)\)，截面排序是 \(O(N\lg N)\)，这一个对比就决定了优化的优先级。
- 截面统计与选股。 分位数、去极值、MAD 标准化、Top-K、十分组断点都是选择问题，线性时间就能完成，不需要全排序（第 06–09 章）。Kendall \(\tau\) 可以用归并排序在 \(O(n\lg n)\) 内算出（第 01、14 章）。
- 订单簿与交易系统。 价格-时间优先撮合用堆或平衡树，价位队列用双向链表加散列表，按 tick 寻址用数组或分层位图，深度查询用扩张的平衡树（第 06、10、11、12、14、18 章）。滚动指标用环形缓冲区和单调队列（第 10、17 章）。
- 路径决策。 最优执行、带交易成本的调仓、最多 \(k\) 次买卖、HMM 市场状态解码都是动态规划（第 15a、15b 章）；选股约束何时可以贪心、何时必须 DP，由拟阵理论判断（第 16 章）。
- 网络与组合。 相关性网络的最小生成树和层次风险平价（第 21、23 章），外汇套利即负权环检测（第 24、25 章），资金调拨即最大流（第 26 章），指数跟踪、CVaR 和无套利检验是线性规划（第 29 章）。
- 数值与信号。 LUP 分解、Cholesky、最小二乘的数值稳定性（第 28 章）；FFT 用于卷积、自相关、周期图、损失分布和期权定价（第 30 章）。
- 知道什么时候该放弃精确解。 基数约束、整手凑预算、0-1 机会选择是 NP 难的（第 34 章），应转向近似算法并用下界评估启发式（第 35 章）。
- 并行与工程。 参数扫描回测的加速比上限由工作量与跨度决定（第 27 章）；摊还 \(O(1)\) 不等于最坏 \(O(1)\)，低延迟路径要预分配（第 17 章）。
1.4 与其他各册的关系
| 相关分册 | 衔接内容 | 本册对应章节 |
|---|---|---|
| 第 01 册 线性代数与矩阵分析 | 本册第 28 章从算法角度讲 LUP、Cholesky、最小二乘；矩阵理论（QR 见第 02a 章，SVD 见第 02b 章，条件数见第 05b 章，Cholesky 见第 07a 章，Schur 补见第 07d 章）以第 01 册为准 | 28、A.5 |
| 第 02 册 概率论 | 指示器随机变量、期望线性性、几何与二项分布、尾界；本册第 05 章和附录 A.4 只列公式 | 05、07、09、11、A.4 |
| 第 03 册 数理统计与统计推断 | 置换检验、多重检验与 FDR（第 10b 章）、bootstrap | 05、27、31 |
| 第 04 册 数值最优化 | 第 04 册第 13、14 章从数值角度讲单纯形法的矩阵实现与内点法，第 12 章讲 KKT，第 16a、16b 章讲二次规划；本册第 29 章侧重单纯形的组合结构、对偶与证明，二者互补 | 15b、16、28、29、34 |
| 第 05 册 计量经济学 | 分位数回归的带权中位数条件、多重共线性 | 09、28 |
| 第 06 册 金融时间序列 | ACF 与周期图（第 02a 章）、Markov 转换模型（第 12b 章）、协方差收缩与因子模型（第 09 章） | 15b、23、30、A.5 |
| 第 07 册 市场微观结构与交易 | 订单簿规则、队列位置、执行算法与冲击成本；本册提供其背后的数据结构和 DP | 06、10、12、14、15b、18 |
| 第 08 册 期权期货与衍生品 | 二叉树美式期权倒推（DP）、Crank-Nicolson 的三对角求解、FFT 定价、无套利与状态价格 | 15b、28、29、30 |
| 第 11 册 量化交易综合实战 | 因子风险模型的计算顺序、执行与回测工程 | 15a、15b、27 |
2. 前置知识与自测
需要的数学不多：数学归纳法、求和与对数的基本运算、离散概率（期望、独立、二项分布），以及一点线性代数（矩阵乘法、线性方程组）。编程方面要能读写 Python 函数、递归和类，会用 numpy 数组。原书默认读者学过离散数学，缺的部分可以先翻本册附录 A。下面 5 题能在半小时内做出 4 题，就可以直接开始。
- 计算 \(\sum_{k=0}^{n}2^k\) 和 \(\sum_{k\ge1}k/2^k\)；说明为什么 \(\sum_{k=1}^n1/k\) 随 \(n\) 增长但增长得很慢。 要点：\(2^{n+1}-1\)；\(\sum kx^k=x/(1-x)^2\) 在 \(x=1/2\) 处为 2；调和数 \(H_n=\ln n+O(1)\)。第一个和式是第 06 章建堆线性时间、第 17 章动态表摊还分析的核心。
- \(n\) 只股票的收益排名是一个均匀随机排列。名次恰好等于股票编号的股票，期望有几只？ 要点：设指示器 \(X_i=I\{\text{第 }i\text{ 只名次为 }i\}\)，\(E[X_i]=1/n\)，由期望线性性 \(E[\sum X_i]=1\)，不需要独立性。这就是第 05 章的核心技巧。
- 用数学归纳法证明：若 \(T(1)=0\)、\(T(n)=2T(n/2)+n\)（\(n\) 为 2 的幂），则 \(T(n)=n\lg n\)。 要点：\(T(n)=2\cdot\frac n2\lg\frac n2+n=n(\lg n-1)+n=n\lg n\)。这是归并排序的运行时间（第 01 章），第 04b 章的主定理会把这类计算一般化。
- 写一个函数求斐波那契数 \(F_n\)。朴素递归
f(n)=f(n-1)+f(n-2)为什么慢？怎样改成线性时间？ 要点：同一子问题被反复计算，调用次数随 \(n\) 指数增长（约 \(\phi^n\)）；用字典缓存或自底向上循环即为 \(\Theta(n)\)。这是第 15a 章「重叠子问题」的最小例子。 - 三种货币的兑换率满足 \(R_{AB}R_{BC}R_{CA}>1\)。把它改写为一个加法不等式，并说明这对图算法意味着什么。 要点：取 \(w=-\ln R\)，条件变为 \(w_{AB}+w_{BC}+w_{CA}<0\)，即图中存在负权环。第 24 章用 Bellman-Ford 检测它，就是三角套利检测。
如果第 1、3 题不顺，先读附录 A.1 和第 03 章；第 2 题不顺，先读第 02 册第 07a 章或附录 A.4。
3. 章节地图
学时按读正文、跑代码、做 5 道练习估算。「必学」是量化研究和交易工程都会用到的内容；「选学」视方向而定；「速读」只需了解结论和适用场景，用到时再回来细看。
| 文件 | 原书章节 | 一句话内容 | 学时 | 标记 |
|---|---|---|---|---|
| 01 算法与算法分析入门 | 第 1–2 章 | 循环不变式、RAM 模型、插入排序与归并排序；用逆序对算 Kendall \(\tau\) | 4 | 必学 |
| 03 函数的增长与渐近记号 | 第 3 章 | 五种渐近记号与增长阶梯；用 log-log 斜率估算量化流程成本，滚动统计降到 \(\Theta(n)\) | 3 | 必学 |
| 04a 分治：最大子数组与 Strassen | 4.1–4.2 | 最大子数组与 Kadane 扫描，最大回撤是最小子数组；Strassen 与 BLAS 的真实成本 | 3 | 必学 |
| 04b 递归式求解与主定理 | 4.3–4.6 | 代入法、递归树、主定理及其空隙；HRP 递归二分的复杂度 | 4 | 必学 |
| 05 概率分析与随机算法 | 第 5 章 | 指示器变量、Fisher–Yates 洗牌、生日悖论、连续正面；作为连涨、创新高、置换检验的零假设基准 | 4 | 必学 |
| 06 堆与优先队列 | 第 II 部分导言、第 6 章 | 建堆线性时间、优先队列与句柄；价格-时间优先订单簿、双堆滚动中位数、多路行情归并 | 4 | 必学 |
| 07 快速排序 | 第 7 章 | 划分不变式、随机化期望 \(1.39n\lg n\)、三路划分与 introsort；排序稳定性与多键排序 | 3 | 必学 |
| 08 排序的下界与线性时间排序 | 第 8 章 | 决策树下界，计数、基数、桶排序；价格档位直方图、区间计数与分位数分组 | 3 | 选学 |
| 09 中位数与顺序统计量 | 第 9 章 | 随机选择与中位数的中位数；截面分位数、去极值、MAD 标准化、带权中位数 | 3 | 必学 |
| 10 基本数据结构 | 第 III 部分导言、第 10 章 | 栈、队列、链表、自由表；环形缓冲区、单调队列、价位委托队列的 \(O(1)\) 撤单 | 3 | 必学 |
| 11 散列表 | 第 11 章 | 链接法、开放寻址、全域与完全散列；代码表索引、容量规划与尾延迟 | 3 | 必学 |
| 12 二叉搜索树与红黑树 | 第 12–13 章 | BST 操作、红黑树性质与修复；订单簿价位的平衡树、tick 数组、排序数组三种实现取舍 | 4 | 选学 |
| 14 数据结构的扩张 | 第 14 章 | 顺序统计树、区间树；订单簿深度与穿透价位、滚动排名、在册订单区间查询 | 3 | 选学 |
| 15a 动态规划：原理与经典问题 | 第 15 章（15.1–15.5） | 最优子结构、重叠子问题、四个经典问题；风险模型矩阵链的计算顺序 | 5 | 必学 |
| 15b 动态规划：量化交易中的应用 | 第 15 章思考题延伸（本册新增） | 最多 \(k\) 次买卖、带成本调仓的无交易区间、离散最优执行、Viterbi 状态解码 | 4 | 必学 |
| 16 贪心算法 | 第 16 章 | 活动选择、Huffman、拟阵；行业约束选股何时可贪心，资金与整手约束为何不行 | 4 | 必学 |
| 17 摊还分析 | 第 17 章 | 聚合、核算、势能三种方法与动态表；摊还 \(O(1)\) 与最坏 \(O(1)\)、抖动与环形缓冲区 | 3 | 选学 |
| 18 B 树、斐波那契堆与 vEB 树 | 第 V 部分导言、第 18–20 章 | B/B+ 树与行情库联合索引；斐波那契堆复杂度；vEB 与订单簿分层位图 | 4 | 速读 |
| 21 不相交集合 | 第 21 章 | 按秩合并与路径压缩、\(\alpha(n)\)；相关性阈值分组与单链接聚类、证券标识归并 | 2 | 选学 |
| 22 基本图算法 | 第 VI 部分导言、第 22 章 | BFS、DFS、拓扑排序、强连通分量、关节点；因子管线依赖与增量重算、风险传导关键节点 | 4 | 必学 |
| 23 最小生成树 | 第 23 章 | 切割性质、Kruskal 与 Prim；Mantegna 相关性 MST 与层次风险平价（HRP）完整实现 | 4 | 必学 |
| 24 单源最短路径 | 第 24 章 | 松弛框架、Bellman-Ford、DAG、Dijkstra、差分约束；外汇三角套利检测 | 4 | 必学 |
| 25 所有结点对的最短路径 | 第 25 章 | \((\min,+)\) 矩阵乘法、Floyd-Warshall、Johnson 重新赋权；最优兑换表与套利资产定位 | 3 | 选学 |
| 26 最大流 | 第 26 章 | 最大流最小割、Edmonds-Karp、二分匹配；保证金资金调拨与策略上线的项目选择 | 4 | 选学 |
| 27 多线程算法 | 第 VII 部分导言、第 27 章 | 工作量、跨度与贪心调度界；参数扫描回测的加速比、竞争条件、EWMA 的并行前缀 | 3 | 选学 |
| 28 矩阵运算 | 第 28 章 | LUP 分解、不求逆、SPD 与 Cholesky、最小二乘；条件协方差、对冲残余风险、三次样条收益率曲线 | 4 | 必学 |
| 29 线性规划 | 第 29 章 | 建模、单纯形、对偶与影子价格、两阶段法；L1 指数跟踪、CVaR、Farkas 引理与无套利 | 6 | 必学 |
| 30 多项式与快速傅里叶变换 | 第 30 章 | 单位复根、FFT、卷积定理与补零；滚动加权统计、周期图、损失分布、Carr–Madan 定价 | 5 | 必学 |
| 31 数论、字符串匹配与计算几何 | 第 31–33 章 | 模运算与 RSA、Miller–Rabin、KMP、凸包；检验的后验、K 线形态流式识别、凸包与有效前沿 | 5 | 速读 |
| 34 NP 完全性 | 第 34 章 | P、NP、归约链；基数约束与整手凑预算为何 NP 难，以及应对办法 | 4 | 选学 |
| 35 近似算法 | 第 35 章 | 顶点覆盖、TSP、集合覆盖、LP 舍入、子集和 FPTAS；用下界评估启发式 | 4 | 选学 |
| A 附录：数学背景速查 | 附录 A–D | 求和定界、关系与树、计数概率与尾界、矩阵秩与正定；EWMA 半衰期、样本协方差何时奇异 | 3 | 速读 |
全册合计约 119 学时。
4. 学习路径
4.1 量化研究速成路径（约 62 学时）
目标是尽快拿到量化研究里最常用的算法工具：会估算成本，会写截面统计和动态规划，会用图和线性规划建模。只读每章的核心小节和量化实战，证明可以跳过。
- 01 全章（4 学时）→ 03 全章（3）→ 04a 4.1 节与量化实战一（3）→ 04b 4.5 主方法与量化实战（2）。打下复杂度分析的底子。
- 05 5.2、5.3、5.4 节与量化实战（4）。零假设基准和正确的洗牌。
- 06 6.5 节与 6.6 节（4）→ 09 9.2 节与 9.5 节（3）→ 10 10.6 节（2）。截面统计与流式指标。
- 15a 15.1–15.5 节与 15.8 节（5）→ 15b 全篇（4）。路径决策问题的标准建模方法。
- 22 22.2–22.5 节与 22.8 节（3）→ 23 23.2–23.4 节与 23.6 节（4）→ 24 24.2、24.3、24.5 节与 24.9 节（4）。相关性网络、HRP、套利检测。
- 28 28.1、28.3、28.4 节与 28.5 节（4）→ 29 29.3–29.5 节与 29.8 节（6）→ 30 30.2、30.5 节与 30.8 节（5）。数值稳定、LP 建模、卷积与谱分析。
- 34 34.1、34.4 节与 34.6 节（2）。学会识别 NP 难的组合构建问题，知道何时转向近似或整数规划。
4.2 完整系统路径（约 119 学时）
按文件顺序通读全册，每章完成「练习」中的基础题和至少两道进阶题，并做「原书推荐习题」里标为强烈推荐的题目。建议分四段推进：
- 第一段：基础与排序（第 01–09 章，约 31 学时）。 重点是循环不变式、主定理、指示器随机变量三件工具，后面所有章节都要用。
- 第二段：数据结构与设计技术（第 10–17 章，约 29 学时）。 第 12 章红黑树的删除修复可以先跳过，读完第 14 章再回头看。第 16 章的拟阵部分是选读，但对理解「约束选股何时可以贪心」很有用。
- 第三段：高级结构与图（第 18–26 章，约 25 学时）。 第 18 章以结论为主；第 21 章的 \(\alpha(n)\) 分析是选读。第 24、25、29 章的「势函数 / 无套利 / 对偶变量」是同一个思想，建议连起来读。
- 第四段：专题（第 27–35 章与附录，约 34 学时）。 第 28、29 章要和第 01、04 册对照着读；第 31 章三部分相互独立，可按兴趣选读。
4.3 交易系统工程专题路径（约 27 学时，可选）
面向写撮合模拟器、行情处理和回测引擎的读者。顺序为：06（订单簿与事件队列）→ 10（价位队列、对象池、环形缓冲区）→ 11（订单索引与容量规划）→ 12（价位的有序结构）→ 14（深度查询）→ 17（延迟尖峰与预分配）→ 18 18.2、18.4、18.5 节（行情库索引与分层位图）→ 08 8.5 节（按 tick 寻址）→ 27（并行回测与竞争条件）。读完后配合第 07 册第 04a、06 章的撮合代码一起看。
5. 本册核心公式与概念速查
| # | 概念 | 公式 / 结论 | 出处 |
|---|---|---|---|
| 1 | 循环不变式 | 初始化、保持、终止三步，相当于「在循环结束处停下」的归纳法 | 01 |
| 2 | 归并排序 | \(T(n)=2T(n/2)+\Theta(n)=\Theta(n\lg n)\)，稳定，额外空间 \(\Theta(n)\) | 01 |
| 3 | 逆序对与 Kendall \(\tau\) | \(\tau=1-\dfrac{4I}{n(n-1)}\)，\(I\) 用归并排序 \(O(n\lg n)\) 计数 | 01、14 |
| 4 | 渐近记号 | \(f=\Theta(g)\iff f=O(g)\wedge f=\Omega(g)\)；\(f=o(g)\iff f/g\to0\) | 03 |
| 5 | 增长阶梯 | \(\lg^*n\ll\lg n\ll n^\epsilon\ll n\ll n\lg n\ll n^2\ll c^n\ll n!\) | 03 |
| 6 | Stirling | \(n!=\sqrt{2\pi n}(n/e)^n(1+\Theta(1/n))\)，\(\lg n!=\Theta(n\lg n)\) | 03、08 |
| 7 | 最大回撤 | 对数收益的最小子数组和 \(m\)，回撤 \(=1-e^{m}\)；Kadane 扫描 \(\Theta(n)\) | 04a |
| 8 | 主定理 | 比较 \(f(n)\) 与 \(n^{\log_ba}\)：叶主导 \(\Theta(n^{\log_ba})\)；相当时乘 \(\lg n\)；根主导（加正则条件）\(\Theta(f(n))\) | 04b |
| 9 | 指示器变量 | \(E[I\{A\}]=\Pr\{A\}\)；期望线性性不需独立 | 05 |
| 10 | 零假设基准 | 随机顺序下创新纪录 \(H_n\approx\ln n\) 次；随机游走创新高约 \(2\sqrt{n/\pi}\) 次；最长连续正面 \(\Theta(\lg n)\) | 05 |
| 11 | 建堆 | \(\sum_h\lceil n/2^{h+1}\rceil O(h)=O(n)\) | 06 |
| 12 | 随机化快排 | \(\Pr\{z_i,z_j\text{ 被比较}\}=\dfrac{2}{j-i+1}\)，期望 \(2n\ln n\approx1.39n\lg n\) 次比较 | 07 |
| 13 | 比较排序下界 | 决策树叶子 \(\ge n!\)，高度 \(\ge\lg n!=\Omega(n\lg n)\) | 08 |
| 14 | 线性时间选择 | 随机选择期望 \(O(n)\)；中位数的中位数 \(T(n)\le T(\lceil n/5\rceil)+T(7n/10+6)+O(n)=O(n)\) | 09 |
| 15 | 带权中位数 | 最小化 \(\sum w_i\lvert x_i-p\rvert\)；MAD 标准化 \(z=(x-\text{med})/(1.4826\cdot\text{MAD})\) | 09 |
| 16 | 散列表 | 装载因子 \(\alpha=n/m\)；链接法 \(\Theta(1+\alpha)\)；开放寻址不成功搜索 \(\le1/(1-\alpha)\) | 11 |
| 17 | 红黑树高度 | \(h\le2\lg(n+1)\)；插入至多 2 次、删除至多 3 次旋转 | 12 |
| 18 | 扩张定理 | 只依赖结点和两个孩子的属性可在插删中维护，保持 \(O(\lg n)\) | 14 |
| 19 | 动态规划 | 最优子结构（子问题独立）+ 重叠子问题；时间 ≈ 子问题数 × 每个子问题的选择数 | 15a |
| 20 | 矩阵链 | \(m[i,j]=\min_k\{m[i,k]+m[k+1,j]+p_{i-1}p_kp_j\}\)；风险计算先投影到因子空间 | 15a |
| 21 | Bellman 方程 | \(V_t(s)=\max_a\{r_t(s,a)+V_{t+1}(s')\}\)，共享资源必须放进状态 | 15b |
| 22 | 线性—二次最优执行 | \(x_k=X\dfrac{\sinh(\kappa(N-k))}{\sinh(\kappa N)}\)，\(2(\cosh\kappa-1)=b/a\) | 15b |
| 23 | Viterbi | \(\delta_t(j)=\max_i\{\delta_{t-1}(i)+\log A_{ij}\}+\log f_j(r_t)\)，\(O(TS^2)\)；属于平滑，回测有前视偏差 | 15b |
| 24 | 贪心与拟阵 | 加权拟阵上「按权递减、能加就加」必最优；分区约束选股是拟阵，预算约束不是 | 16 |
| 25 | 势能法 | \(\hat c_i=c_i+\Phi(D_i)-\Phi(D_{i-1})\)；动态表 \(\Phi=2num-size\)，插入摊还 3 | 17 |
| 26 | B 树高度 | \(h\le\log_t\dfrac{n+1}{2}\)，磁盘访问 \(O(\log_tn)\) | 18 |
| 27 | 并查集 | 按秩合并 + 路径压缩 \(O(m\,\alpha(n))\)，实际 \(\alpha(n)\le4\) | 21 |
| 28 | BFS / DFS | \(O(V+E)\)；有向图无环 \(\iff\) DFS 无后向边；拓扑序 = 完成时间递减 | 22 |
| 29 | 切割性质 | 尊重 \(A\) 的切割上的轻量级边对 \(A\) 安全；Kruskal、Prim \(O(E\lg V)\) | 23 |
| 30 | 相关性距离与 HRP | \(d_{ij}=\sqrt{2(1-\rho_{ij})}\)；递归二分 \(\alpha=1-V_1/(V_1+V_2)\) | 23 |
| 31 | 套利检测 | \(w=-\ln R\)，\(\prod R>1\iff\sum w<0\)；无负权环 \(\iff\exists h:\ w(i,j)+h_i-h_j\ge0\) | 24、25 |
| 32 | 最短路径算法 | Bellman-Ford \(O(VE)\)；Dijkstra（非负权）\(O((V+E)\lg V)\)；Floyd-Warshall \(\Theta(n^3)\)，\(d_{ii}<0\) 即负环 | 24、25 |
| 33 | 最大流最小割 | 最大流值 = 最小割容量；Edmonds-Karp \(O(VE^2)\)；项目选择净收益 \(=\sum p_i-\) 最小割 | 26 |
| 34 | 并行性能 | \(T_P\ge\max(T_1/P,\ T_\infty)\)；贪心调度 \(T_P\le T_1/P+T_\infty\) | 27 |
| 35 | LUP 与最小二乘 | \(PA=LU\) 分解 \(\Theta(n^3)\)、求解 \(\Theta(n^2)\)；\(\kappa(A^TA)=\kappa(A)^2\)，共线时用 QR/SVD | 28 |
| 36 | 舒尔补 | \(S=C-BA^{-1}B^T\) 是条件协方差，也是最小方差对冲后的残余风险 | 28 |
| 37 | LP 对偶 | \(\max\{c^Tx:Ax\le b,x\ge0\}=\min\{b^Ty:A^Ty\ge c,y\ge0\}\)；对偶变量即影子价格 | 29 |
| 38 | Farkas 引理 | 无套利 \(\iff\) 存在非负状态价格 | 29 |
| 39 | 卷积定理 | \(a\otimes b=\mathrm{DFT}^{-1}_{2n}(\mathrm{DFT}_{2n}(a)\cdot\mathrm{DFT}_{2n}(b))\)，必须补零，否则是循环卷积 | 30 |
| 40 | 近似比 | 顶点覆盖 2、度量 TSP 2、集合覆盖 \(H(\max\lvert S\rvert)\le\ln\lvert X\rvert+1\)、子集和 FPTAS \(1+\epsilon\) | 35 |
6. 勘误汇总
6.1 精读笔记与正文更正
- 15a_动态规划原理与经典问题.md：精读笔记把最优二叉搜索树例题的根表记作 \(root[2,5]=5\)，按递归式计算应为 \(root[2,5]=4\)（等于 5 的是 \(root[3,5]\)）。统稿时用原书数据重新计算，确认期望搜索代价 2.75、\(root[1,5]=2\)、\(root[2,5]=4\)、\(root[3,5]=5\)，正文的勘误说明正确。
- 04a_分治算法_最大子数组与Strassen矩阵乘法.md：原书写作时矩阵乘法指数的最好上界是 Coppersmith–Winograd 的 \(O(n^{2.376})\)，正文按原书表述并注明「原书写作时」。此后上界已有小幅改进（约 2.37），对本章结论没有影响。
统稿时抽查了各章练习中有数值答案的题目（如 01 题 3、04a 题 8、05 题 4/5/9、11 题 5/6、24 题 6、29 题 3、30 题 1、31 题 2–4），答案均正确，没有发现原书错误需要列入。
6.2 统稿时修正的交叉引用
本册合并、拆分章节后，旧的「第 X 章」写法有一部分指向了不存在的文件，统稿时已改正：
- 01：凸包「第 33 章」改为「原书第 33 章，本册第 31 章第三部分」；LCS「第 15 章」改为第 15a 章。
- 06：插入排序、归并排序「第 2 章」改为第 01 章；主定理「第 4 章」改为第 04b 章；斐波那契堆、vEB 树补注「本册第 18 章」。
- 07：「第 2 章、第 4 章」改为第 01 章、第 04a 章。
- 24：斐波那契堆「第 19 章」改为第 18 章；动态规划「第 15 章」改为第 15a 章。25 同样改为第 15a 章。
- 26：最小费用流的 LP 写法指向第 29 章 29.3.3 节（原写 29.2 节，那是标准型一节）。
- 27：第七部分导言里本册与原书章号的对应关系重写为一句准确说明。
- 28：第 01 册章号改为实际文件（QR 第 02a 章、SVD 第 02b 章、条件数第 05b 章、Cholesky 第 07a 章、Schur 补第 07d 章）。
- 29、31、34：二次规划「第 04 册第 16 章」改为第 16a、16b 章；31 多重检验「第 03 册第 10 章」改为第 10b 章。
- A：第 02 册章号改为 04a、04b、07a 章；第 01 册改为第 00 章与第 07a–07d 章；扫描线「第 33 章」改为第 31 章第三部分。
- 04b 与 23：HRP 的中文名统一为「层次风险平价」，两章互相加了引用；A A.3.3 节加了指向第 21、23 章的引用。
- 15a、15b：标题统一为「第 15a 章」「第 15b 章」。
6.3 需要回查原书的地方
- 18：斐波那契堆与 vEB 树只讲思路和复杂度，完整伪代码、B 树删除的全部情形和最大度数界的证明见原书 PDF p.520–523、p.531–547、p.557–577。
- 21 21.4 节：\(O(m\,\alpha(n))\) 的势函数证明只给骨架，细节见原书 PDF p.594–603。
- 26 26.4 节：推送-重贴标签与前置重贴标签只讲思想与界，证明见原书 PDF p.757–781。
- 34：Cook–Levin 电路构造和 HAM-CYCLE 的 12 顶点部件只保留思路，细节见原书 PDF p.1088–1099、p.1112–1118。
- 31 31.3 节：模运算的群论严格化只列要点，见原书 31.3 节（PDF p.960–967）。
- 04b 4.7 节 Akra–Bazzi 方法、08 8.6 节的其他思考题：只给结论，需要时回原书。
- 30 的「原书对照」：30.3–30.5 节都落在原书 30.2 节（PDF p.927–936）内，只标了「同上」，没有逐小节分页。
- 几处「原书对照」页码区间首尾相接或略有重叠（如 21.2/21.3、34.5.7/34.5.8、35.2–35.4、A.2/A.3），这是小节在同一页内衔接造成的，按起始页翻即可。
7. 配套代码说明
7.1 运行环境
本册代码为 Python 3（3.10 及以上），实际用到的库为 numpy、scipy、scikit-learn（只在第 21、23 章用 adjusted_rand_score 评估聚类）以及标准库（heapq、collections、bisect、itertools、concurrent.futures 等）。全册通用环境写作 numpy/pandas/scipy/statsmodels/scikit-learn/arch，本册没有用到 pandas、statsmodels、arch 的专有功能。scipy 要求 1.9 以上（第 35 章用 scipy.optimize.milp，第 26 章用 scipy.sparse.csgraph.maximum_flow；做第 30 章练习 9 还要用 scipy.linalg.matmul_toeplitz）。
全册共约 140 段 Python 代码。统稿时在 numpy 2.x、scipy 1.18 下逐段运行，除下面列出的有依赖关系的段落外，每段都能独立运行；所有随机实验都固定了随机种子，正文里的输出可以复现（计时类数字随机器不同）。整册代码在 8 核机器上并行跑完不到 10 秒。
7.2 两类代码块
- 伪代码对照块。 第 10、11、12、14、16、21–26、29 章正文里有不少用 Python 语法写的原书伪代码（函数名大写，如
CHAINED_HASH_INSERT、MST_KRUSKAL、PIVOT），它们引用NIL、MAKE_SET、MinPriorityQueue之类的抽象对象，用来和原书逐行对照，不是可独立运行的程序。其中含非 Python 语句的几段（第 14 章旋转时更新size的两行、第 17 章TABLE_INSERT、第 23 章GENERIC_MST、第 29 章SIMPLEX与INITIALIZE_SIMPLEX）统稿时已把代码块标为text。 - 可运行块。 每章「量化实战」一节的代码都是完整程序，开头自带 import 和模拟数据，可以直接复制运行。
7.3 有依赖关系的代码
本册没有跨章的代码依赖：每章的实战代码都自带所需函数（例如第 23 章的 HRP 代码自己实现了并查集与 Kruskal，不依赖第 21 章），不需要先运行其他章节。章内依赖有以下四处，正文代码里都有注释说明：
| 章节 | 依赖 | 运行方式 |
|---|---|---|
| 26 最大流 26.6.2、26.6.3 节 | 用到 26.6.1 节定义的 edmonds_karp，26.6.3 节还用到 26.6.2 节的 import itertools |
三段放在同一个文件或同一个 Jupyter 会话中依次运行 |
| 29 线性规划 29.8.1 节 | 验证脚本 from simplex import simplex |
先把 29.8.1 节的单纯形实现保存为 simplex.py，与验证脚本放在同一目录 |
| 30 多项式与 FFT 30.6.5 节 | 验证脚本用到前两段的 recursive_fft、bit_reverse_copy、iterative_fft |
与 30.4.2 节（递归 FFT）、30.6.3 节（迭代 FFT）的两段实现一起运行 |
| 31 数论、字符串匹配与计算几何 31.10.3 节 | 用到第二部分定义的 compute_prefix_function、kmp_matcher、rabin_karp |
与第二部分 32.2 节（Rabin–Karp）、32.4 节（KMP）的两段实现一起运行 |
统稿时已按上表的方式把这四组代码合并运行，结果与正文一致。