第 04b 章 递归式求解：代入法、递归树与主定理

本章对应原书 4.3–4.6 节与第 4 章思考题。分治算法的运行时间天然写成递归式，例如归并排序 \(T(n)=2T(n/2)+\Theta(n)\)、Strassen \(T(n)=7T(n/2)+\Theta(n^2)\)。本章给出三种求解方法：代入法（猜测 + 归纳证明）、递归树法（逐层求和，适合产生猜测）、主方法（套公式）。主定理是全书使用频率最高的工具之一，必须熟练；它的证明（4.6 节，带 ★）可以选读，但其中"叶子主导、各层均衡、根主导"的递归树图景值得理解，它让你看一眼递归式就知道成本花在哪里。

学习目标

1. 会用代入法证明递归式的上下界，掌握"选择 \(n_0\) 处理边界""减去低阶项强化假设""变量替换"三种技巧，并能识别"证明了 \(T(n)\le cn+n\) 就说是 \(O(n)\)"这类错误。
2. 会画递归树，逐层求和得到猜测，能处理不等分割的递归式。
3. 熟记主定理三种情况及其条件（多项式差距、正则条件），能识别主定理不适用的"空隙"。
4. 理解主定理证明的结构：引理 4.2 的递归树求和、引理 4.3 的三种几何级数。
5. 了解主定理的推广（\(\lg^kn\) 因子的情况 2 扩展、Akra–Bazzi 方法），知道何时需要回原书。
6. 能用递归式分析量化中的分治/递归算法，例如层次风险平价（HRP）的递归二分配权。

读前导读

这一章在解决什么问题

前两章写出了一串"递归式"：归并排序 \(T(n)=2T(n/2)+\Theta(n)\)，Strassen \(T(n)=7T(n/2)+\Theta(n^2)\)。递归式只说了"大问题的耗时 = 几个小问题的耗时 + 拆分合并的耗时"，并没有直接告诉我们 \(T(n)\) 到底是多少。这一章教你把它"解"出来，变成 \(\Theta(n\lg n)\)、\(\Theta(n^{2.807})\) 这样能直接比较的结论。

最实用的工具是主定理，它其实只在做一件事：比较"递归树每往下一层，总工作量是变多还是变少"。仍然用"数据量翻倍"来想：以 \(b=2\) 为例，规模翻倍时，子问题数量乘 \(a\)（叶子那一层的工作量乘 \(a\)），而顶层的拆分合并费用 \(f(n)\) 乘 \(f(2n)/f(n)\)。

• 如果 \(a\) 更大（例如 Strassen：叶子乘 7，顶层 \(n^2\) 只乘 4），大部分工作在最底层，答案由叶子数决定。
• 如果两者一样（例如归并排序：叶子乘 2，顶层 \(n\) 也乘 2），每一层工作量相同，答案 = 每层工作量 × 层数。
• 如果顶层更大（例如 \(2T(n/2)+n^2\)：叶子乘 2，顶层乘 4），工作量越往下越少，答案由顶层决定。

这个图景你在 CFA 里早就见过：它就是几何级数。每层工作量构成一个等比数列，公比小于 1 时总和约等于首项（像永续年金的现值，由最近的现金流主导），公比等于 1 时总和 = 首项 × 期数，公比大于 1 时总和由最后一项主导（像增长率高于贴现率的增长年金，越远的现金流越重要）。

代入法和递归树法是主定理的"手工版"：前者像审计里的"先提出假设，再逐笔验证"，后者像把成本按组织层级逐层汇总。

需要先想起来的数学

• 几何级数求和。 \(1+r+r^2+\cdots+r^{k-1}=\frac{1-r^k}{1-r}\)；\(|r|<1\) 时无穷项之和为 \(\frac{1}{1-r}\)。例：\(r=3/16\) 时无穷和为 \(\frac{16}{13}\approx1.23\)，所以首项占了总和的八成以上。年金现值公式就是它。详见 第 00 册第 04 章 级数与收敛。
• 对数恒等式。 \(a^{\log_bn}=n^{\log_ba}\)（第 03 章 3.3 节），它把"\(a\) 的层数次方"变成"\(n\) 的某次幂"。例：\(7^{\lg n}=n^{\lg 7}\)；\(n=1024\) 时两边都是 \(7^{10}\approx2.8\times10^8\)。还要会 \(\lg(n/2)=\lg n-1\)。
• 数学归纳法（强归纳）。 代入法的"假设对所有 \(m<n\) 成立，证明对 \(n\) 成立"是强归纳：可以借用任何更小的情形，而不只是 \(n-1\)。详见 第 00 册第 08 章 读懂数学证明与符号。
• 调和级数。 \(1+\frac12+\frac13+\cdots+\frac1k\approx\ln k\)。它在"空隙"情形和思考题里出现。详见 第 00 册第 04 章 级数与收敛。
• 积分（只在 Akra–Bazzi 处用到）。 \(\int_1^n\frac1u\,du=\ln n\)。详见 第 00 册第 03 章 积分。

怎么读这一章

必读的是 4.5 节主定理（定理陈述、"直觉"一小节和例子表）以及 4.4 节递归树例 1、例 2。读完这些就能应付全书绝大多数分析。4.3 节代入法第一次读只看第一个例子和"一个常见陷阱"，"减去低阶项""变量替换"可以第二遍再看。4.6 节带 ★ 的主定理证明可以跳过，但建议至少读引理 4.2 和三种几何级数那几行，它们就是上面"三种情况"的严格版本；"推广到取整"可以完全跳过。4.7 节是速查表和延伸，查阅即可。量化实战里 HRP 的复杂度分析值得一读，它是主定理情况 3 的一个干净例子。

预备：递归式的技术细节

先说清楚哪些细节可以忽略。

取整。 \(n\) 为奇数时，归并排序两个子问题的规模是 \(\lfloor n/2\rfloor\) 与 \(\lceil n/2\rceil\)，严格的递归式是

边界条件。 常数规模输入的运行时间是常数，所以足够小的 \(n\) 有 \(T(n)=\Theta(1)\)，通常直接写成 \(T(n)=2T(n/2)+\Theta(n)\)。改变 \(T(1)\) 的值会改变精确解，但通常只差常数因子，不改变增长量级。

一般做法是先忽略取整和边界条件，求出结果后再判断它们是否重要。通常不重要，但要知道什么时候重要。主定理（定理 4.1）表明，对很多分治递归式，这些细节都不影响渐近界。

不等式形式。 \(T(n)\le2T(n/2)+\Theta(n)\) 只给出上界，解用 \(O\) 表示；\(T(n)\ge2T(n/2)+\Theta(n)\) 只给出下界，解用 \(\Omega\) 表示。

4.3 代入法

两个步骤

**代入法（substitution method）**分两步：猜测解的形式；用数学归纳法求出常数并证明解正确。归纳时要把猜测的解"代入"较小参数的函数值，因此得名。它很强大，但前提是能猜出答案。

例： 求 \(T(n)=2T(\lfloor n/2\rfloor)+n\) 的上界。猜 \(T(n)=O(n\lg n)\)，即要证 \(T(n)\le cn\lg n\)（\(c>0\) 待定）。假设对所有 \(m<n\) 成立，特别地 \(T(\lfloor n/2\rfloor)\le c\lfloor n/2\rfloor\lg\lfloor n/2\rfloor\)，代入：

最后一步只要 \(c\ge1\)。

推导拆解：逐步看每个不等号用了什么。 第一个 \(\le\)：把归纳假设 \(T(\lfloor n/2\rfloor)\le c\lfloor n/2\rfloor\lg\lfloor n/2\rfloor\) 代入递归式，前面乘 2、后面加 \(n\)。 第二个 \(\le\)：\(\lfloor n/2\rfloor\le n/2\)，而 \(x\lg x\) 随 \(x\) 增大而增大，所以把 \(\lfloor n/2\rfloor\) 放大成 \(n/2\) 只会让右边更大；\(2\cdot c\cdot\frac n2=cn\)。 等号：\(\lg(n/2)=\lg n-\lg 2=\lg n-1\)（商的对数等于对数之差）。 最后一个 \(\le\)：\(-cn+n\le0\) 等价于 \(c\ge1\)。 注意结论必须精确地落回 \(cn\lg n\) 这个形式，用的是同一个 \(c\)。这就像账户的逐期结转："假设上期期末余额正确，验证本期发生额后，本期期末余额也正确"：每一期都必须对上同一个口径，口径一变，链条就断了。下文"常见陷阱"就是口径悄悄变了：若每层只推出 \(T(n)\le(c+1)n\)，上一层就只能用 \(c+1\)，再上一层用 \(c+2\)……\(\lg n\) 层后常数变成 \(c+\lg n\)，总量其实是 \(n\lg n\)。

边界条件：选择 \(n_0\)

归纳还需要基础情况。若唯一的边界条件是 \(T(1)=1\)，那么 \(n=1\) 时要求 \(T(1)\le c\cdot1\cdot\lg1=0\)，与 \(T(1)=1\) 矛盾，归纳基础不成立。

解决办法是利用渐近记号的灵活性：只要求对 \(n\ge n_0\) 成立，而 \(n_0\) 可以自己选。\(n>3\) 时递归式不会直接用到 \(T(1)\)，所以把 \(T(2)\)、\(T(3)\) 当作归纳证明的基础情况，取 \(n_0=2\)。要区分递归式的基本情况（\(n=1\)）和归纳证明的基础情况（\(n=2,3\)）。由 \(T(1)=1\) 算出 \(T(2)=4\)、\(T(3)=5\)，取 \(c\ge2\) 就有 \(T(2)\le c\cdot2\lg2\)、\(T(3)\le c\cdot3\lg3\)。对大多数递归式，这样扩展边界条件是直接的，以后不再每次写出。

如何猜

没有通用方法，靠经验和一些启发式：

• 与见过的递归式类比。 \(T(n)=2T(\lfloor n/2\rfloor+17)+n\) 看起来难，但 \(n\) 大时 \(\lfloor n/2\rfloor\) 与 \(\lfloor n/2\rfloor+17\) 差别很小，都近似对半分，所以猜 \(O(n\lg n)\)（练习 4.3-6 验证）。
• 先证宽松的上下界再收紧。 对 \(T(n)=2T(\lfloor n/2\rfloor)+n\)，由 \(n\) 这一项得下界 \(\Omega(n)\)，容易证明上界 \(O(n^2)\)，然后逐步降低上界、提高下界，收敛到 \(\Theta(n\lg n)\)。
• 用递归树产生猜测（下一节）。

微妙之处：减去一个低阶项

有时渐近界猜对了，归纳却算不通。原因通常是归纳假设不够强。

例：\(T(n)=T(\lfloor n/2\rfloor)+T(\lceil n/2\rceil)+1\)。猜 \(O(n)\)，试证 \(T(n)\le cn\)：

推不出 \(T(n)\le cn\)。这时不要去猜更大的 \(O(n^2)\)（虽然能证，但不紧）。原来的猜测是对的，只差一个低阶常数。改用更强的假设 \(T(n)\le cn-d\)（\(d\ge0\) 为常数）：

只要 \(d\ge1\)。反直觉的地方在于：证明一个较弱的上界反而可能更难，因为归纳时你也只能用那个较弱的界。递归式里有几个递归项，就能减掉几次低阶项（这里减了两次 \(d\)）。

白话解释：为什么"要求更严"反而更好证？归纳证明里，假设既是你要交的答卷，也是你能用的工具。假设 \(T(n)\le cn\) 时，两个子问题各给你 \(c\cdot\frac n2\) 的额度，合起来正好 \(cn\)，再加上合并的 1，就超支了 1，没有余地。改成 \(T(n)\le cn-d\) 后，每个子问题都"预留"了 \(d\) 的余量，两个子问题一共省出 \(2d\)，付掉合并的 1 之后还剩 \(2d-1\ge d\)，正好够本层再预留一个 \(d\)。就像每个子部门都按预算少报一点作为缓冲，汇总到上一级时就有空间吸收管理费用。数值检查：\(d=1\)、\(c=2\)，若 \(T(1)=1\)，则 \(T(2)=1+1+1=3=2\cdot2-1\)，\(T(4)=3+3+1=7=2\cdot4-1\)，确实一直满足 \(T(n)\le2n-1\)。

练习 4.3-7 与 4.3-8 是同一技巧的练习：\(T(n)=4T(n/3)+n\) 的解是 \(\Theta(n^{\log_34})\)，直接假设 \(T(n)\le cn^{\log_34}\) 会多出一个 \(+n\)，改为 \(T(n)\le cn^{\log_34}-dn\) 即可；\(T(n)=4T(n/2)+n=\Theta(n^2)\) 同理，假设 \(cn^2-dn\)。

一个常见陷阱

对 \(T(n)=2T(\lfloor n/2\rfloor)+n\)，有人这样"证明" \(T(n)=O(n)\)：猜 \(T(n)\le cn\)，于是

错在没有证明归纳假设的精确形式。要证 \(T(n)=O(n)\)，必须明确推出 \(T(n)\le cn\)，而 \(cn+n\) 不满足这个形式。每一步都"是 \(O(n)\)"不等于整体是 \(O(n)\)，因为常数在每层递归都在变大。

变量替换

例：\(T(n)=2T(\lfloor\sqrt n\rfloor)+\lg n\)。先忽略取整，令 \(m=\lg n\)，得 \(T(2^m)=2T(2^{m/2})+m\)。再令 \(S(m)=T(2^m)\)，得

这就是熟悉的形式，\(S(m)=O(m\lg m)\)。换回原变量：\(T(n)=S(\lg n)=O(\lg n\lg\lg n)\)。

推导拆解：关键是 \(\sqrt n\) 在对数尺度上就是"减半"。令 \(n=2^m\)，则 \(\sqrt n=2^{m/2}\)，\(\lg n=m\)。所以原式 \(T(2^m)=2T(2^{m/2})+m\)。再给 \(T(2^m)\) 起个新名字 \(S(m)\)，右边的 \(T(2^{m/2})\) 自然就是 \(S(m/2)\)，得到 \(S(m)=2S(m/2)+m\)，和归并排序一模一样。最后把 \(m=\lg n\) 代回去。这和金融里把价格取对数、把乘法变成加法是同一个思路：换一个尺度，复杂的关系就变成熟悉的形状。

练习 4.3-9 同理：\(T(n)=3T(\sqrt n)+\lg n\)，令 \(m=\lg n\) 得 \(S(m)=3S(m/2)+m=\Theta(m^{\lg3})\)，所以 \(T(n)=\Theta((\lg n)^{\lg3})\)。

4.4 递归树法

代入法给出干净的证明，但难在猜。画**递归树（recursion tree）**是产生好猜测的直接方式：每个结点代表一个子问题的代价，先对每层求和，再把各层相加。用递归树产生猜测时可以容忍一些"不严谨"（忽略取整、假设 \(n\) 是某个数的幂），然后用代入法验证。如果画得足够仔细，递归树本身也能作为严格证明，4.6 节就用它证明主定理。

例 1：\(T(n)=3T(\lfloor n/4\rfloor)+\Theta(n^2)\)

容忍的不严谨：写成 \(T(n)=3T(n/4)+cn^2\)，假设 \(n\) 是 4 的幂。

• 根的代价 \(cn^2\)，有 3 个孩子，各代价 \(c(n/4)^2\)；再下一层 9 个结点，各 \(c(n/16)^2\)。
• 深度 \(i\) 处子问题规模 \(n/4^i\)，\(i=\log_4n\) 时规模为 1，所以树有 \(\log_4n+1\) 层。
• 深度 \(i\)（\(i<\log_4n\)）有 \(3^i\) 个结点，每个代价 \(c(n/4^i)^2\)，该层合计 \(3^ic(n/4^i)^2=(3/16)^icn^2\)。
• 最底层有 \(3^{\log_4n}=n^{\log_43}\) 个叶子，每个代价 \(T(1)\)，合计 \(\Theta(n^{\log_43})\)。

总代价：

各层代价构成递减的几何级数，总和不超过首项的常数倍，根的代价主导总代价。这个上界也是紧的：第一层就贡献了 \(cn^2\)，所以下界是 \(\Omega(n^2)\)。

金融直觉：把每层代价看成一串现金流：第 0 层 \(cn^2\)，第 1 层 \(\frac3{16}cn^2\)，第 2 层 \((\frac3{16})^2cn^2\)……这和"每期现金流按固定比例 \(\frac3{16}\) 衰减的永续年金"完全同构，总和 \(=\frac{\text{首项}}{1-\text{公比}}=\frac{cn^2}{1-3/16}=\frac{16}{13}cn^2\)。首项占了 \(\frac{13}{16}\approx81\%\)，所以说根主导。 公比 \(\frac3{16}\) 从哪来？下一层结点数乘 3，每个结点的规模变成 \(\frac14\)，代价 \(n^2\) 变成 \(\frac1{16}\)，合起来乘 \(\frac3{16}\)。换成"规模放大"的语言：这里每层规模缩小到 \(\frac14\)，所以看 \(n\) 乘 4 的情形。树多一层，叶子数只乘 3，而根的代价 \(n^2\) 乘 16，根的增长快得多，所以根主导。 叶子那一项 \(3^{\log_4n}\) 用了第 03 章的恒等式 \(a^{\log_bn}=n^{\log_ba}\)，得到 \(n^{\log_43}\approx n^{0.79}\)，比 \(n^2\) 小得多，可以忽略。

用代入法验证：证 \(T(n)\le dn^2\)，

只要 \(d\ge\frac{16}{13}c\)。

例 2：不等分割 \(T(n)=T(n/3)+T(2n/3)+O(n)\)

设 \(c\) 为 \(O(n)\) 中的常数。顶部各层的代价都是 \(cn\)（每层子问题规模之和仍为 \(n\)）。从根到叶最长的路径是 \(n\to\frac23n\to(\frac23)^2n\to\cdots\to1\)，长度 \(\log_{3/2}n\)。直观上解至多是"层数 × 每层代价" \(=O(cn\log_{3/2}n)=O(n\lg n)\)。

但要小心：并非每一层都贡献 \(cn\)。如果它是一棵高 \(\log_{3/2}n\) 的完全二叉树，叶子会有 \(2^{\log_{3/2}n}=n^{\log_{3/2}2}\) 个，而 \(\log_{3/2}2>1\)，叶子代价就成了 \(\omega(n\lg n)\)。实际上这棵树不完全：沿 \(1/3\) 分支的路径很快到底，越往下缺的结点越多，底部各层贡献少于 \(cn\)。不必精确核算，直接用代入法验证 \(T(n)\le dn\lg n\)：

只要 \(d\ge c/(\lg3-2/3)\)。

练习 4.4-6 补上下界：最短的根到叶路径长 \(\log_3n\)，在此深度之前每层都是满的 \(cn\)，所以 \(T(n)=\Omega(n\lg n)\)。练习 4.4-9 进一步推广：对任意常数 \(0<\alpha<1\)，\(T(n)=T(\alpha n)+T((1-\alpha)n)+cn\) 的解都是 \(\Theta(n\lg n)\)。任何常数比例的分割都给出 \(n\lg n\)，这是第 7 章快速排序分析的关键直觉：即使每次都按 9:1 分割，快速排序仍是 \(O(n\lg n)\)。

白话解释：为什么不均匀也没关系？每一层所有子问题加起来仍是 \(n\) 个元素，所以每层代价至多 \(cn\)；真正决定总量的是层数。按 9:1 切，最长的那条路径每次只缩到 \(\frac9{10}\)，要切 \(\log_{10/9}n\) 次才到底。\(\log_{10/9}n=\frac{\lg n}{\lg(10/9)}\approx6.6\lg n\)，只是 \(\lg n\) 的常数倍。所以"每层 \(cn\) × 约 \(6.6\lg n\) 层"仍是 \(\Theta(n\lg n)\)，只是常数变大。只有当每次切下的是常数个元素（而不是常数比例）时，层数才会变成 \(n\) 量级，下面表格里的 \(T(n-a)+T(a)+cn\) 就是这种坏情况。

其他递归树练习的答案

\(T(n-a)+T(a)+cn\) 一行值得注意：每次只切掉常数大小的一块，递归深度是 \(n/a\)，每层代价线性，总计平方。这正是快速排序在最坏划分下退化为 \(\Theta(n^2)\) 的原因。

4.5 主方法

主定理

**主方法（master method）**是求解

的"食谱"，其中 \(a\ge1\)、\(b>1\) 为常数，\(f(n)\) 渐近为正。它描述这样的算法：把规模 \(n\) 的问题分成 \(a\) 个规模 \(n/b\) 的子问题递归求解，分解与合并共花 \(f(n)\)。\(n/b\) 可能不是整数，但把 \(T(n/b)\) 换成 \(T(\lfloor n/b\rfloor)\) 或 \(T(\lceil n/b\rceil)\) 不影响渐近行为（4.6 节证明），所以通常省略取整。

定理 4.1（主定理，master theorem） 设 \(a\ge1\)、\(b>1\) 为常数，\(f(n)\) 为函数，\(T(n)\) 在非负整数上由 \(T(n)=aT(n/b)+f(n)\) 定义（\(n/b\) 理解为 \(\lfloor n/b\rfloor\) 或 \(\lceil n/b\rceil\)）。则

1. 若对某常数 \(\epsilon>0\) 有 \(f(n)=O(n^{\log_ba-\epsilon})\)，则 \(T(n)=\Theta(n^{\log_ba})\)。
2. 若 \(f(n)=\Theta(n^{\log_ba})\)，则 \(T(n)=\Theta(n^{\log_ba}\lg n)\)。
3. 若对某常数 \(\epsilon>0\) 有 \(f(n)=\Omega(n^{\log_ba+\epsilon})\)，且对某常数 \(c<1\) 和所有足够大的 \(n\) 有 \(af(n/b)\le cf(n)\)，则 \(T(n)=\Theta(f(n))\)。

直觉

三种情况都是在比较 \(f(n)\) 与 \(n^{\log_ba}\)，较大者决定解：

• \(n^{\log_ba}\) 是递归树的叶子数（\(a^{\log_bn}=n^{\log_ba}\)），代表"解所有最小子问题"的总代价。
• \(f(n)\) 是根的代价，代表"最顶层分解与合并"的代价。
• 情况 1：叶子多项式地更大，叶子主导，\(T=\Theta(n^{\log_ba})\)。
• 情况 2：两者同阶，每层代价都差不多，再乘以层数 \(\lg n\)。
• 情况 3：根多项式地更大，根主导，\(T=\Theta(f(n))\)。

白话解释：用"翻倍"把三种情况算一遍（取 \(b=2\)，设 \(f(n)=n^k\)）。规模 \(n\) 翻倍，递归树多一层，叶子数乘 \(a\)，所以叶子总代价 \(n^{\lg a}\) 翻 \(a\) 倍；根的代价 \(n^k\) 翻 \(2^k\) 倍。谁翻得多，谁说了算。 情况 1，\(a>2^k\)：Strassen 的 \(a=7\)，\(2^k=4\)。叶子翻 7 倍、根翻 4 倍，越往下每层代价越大（公比 \(\frac74>1\)），总和由最底层决定，\(\Theta(n^{\lg7})\)。 情况 2，\(a=2^k\)：归并排序 \(a=2\)、\(k=1\)。每层代价都一样（公比 1），总和 = 一层的代价 × 层数 = \(n\times\lg n\)。 情况 3，\(a<2^k\)：HRP 的 \(2T(n/2)+n^2\)，\(a=2\)，\(2^k=4\)。每往下一层代价减半（公比 \(\frac12\)），总和约等于根的 2 倍，\(\Theta(n^2)\)。 所以背主定理不如记一句话：算出每往下一层代价乘以多少（公比 \(a/b^k\)），大于 1 看叶子，等于 1 乘层数，小于 1 看根。 一个快速检查：\(n\) 翻倍时，情况 1 的总耗时翻 \(a\) 倍，情况 3 翻 \(2^k\) 倍，情况 2 翻"略多于 \(a\) 倍"（多出来的是层数的增加）。

情况 1 要求 \(f\) 多项式地小于 \(n^{\log_ba}\)，即小一个 \(n^\epsilon\) 因子；情况 3 要求 \(f\) 多项式地更大，并且满足正则条件（regularity condition） \(af(n/b)\le cf(n)\)（我们遇到的多项式有界函数大多满足）。三种情况没有覆盖所有可能：

• 情况 1 与 2 之间有空隙：\(f\) 小于 \(n^{\log_ba}\)，但不是多项式地小；
• 情况 2 与 3 之间有空隙：\(f\) 大于 \(n^{\log_ba}\)，但不是多项式地大；
• 情况 3 的正则条件可能不成立。

落入这些地方时主方法不适用，要改用递归树或代入法。

白话解释："多项式地"小或大，意思是两者之比至少差一个 \(n^\epsilon\) 这样的幂次因子（比如 \(n^{0.1}\)），而不只是差一个 \(\lg n\)。用公比的语言说：差一个 \(n^\epsilon\) 时，每层代价的公比严格不等于 1，几何级数要么明显递增、要么明显递减；只差 \(\lg n\) 时，公比"几乎是 1 但又不完全是"，上面三种干净的图景都不成立，要单独算。正则条件 \(af(n/b)\le cf(n)\) 则是要求"下一层的总代价至多是本层的 \(c\) 倍（\(c<1\)）"，也就是保证级数确实在递减，像要求永续年金的增长率严格小于贴现率。

例子

第三行的正则条件验证：\(af(n/b)=3\cdot\frac n4\lg\frac n4\le\frac34n\lg n=cf(n)\)。最后一行是最常见的"空隙"例子：\(n\lg n\) 渐近大于 \(n\)，但比值 \(\lg n\) 对任何 \(\epsilon>0\) 都渐近小于 \(n^\epsilon\)。它的解是 \(\Theta(n\lg^2n)\)，见下文的情况 2 扩展。

练习 4.5-1 的四个递归式是很好的口算练习：\(2T(n/4)+1=\Theta(\sqrt n)\)；\(2T(n/4)+\sqrt n=\Theta(\sqrt n\lg n)\)；\(2T(n/4)+n=\Theta(n)\)；\(2T(n/4)+n^2=\Theta(n^2)\)。练习 4.5-2：若把矩阵分成 \(n/4\times n/4\) 块，分解合并 \(\Theta(n^2)\)，即 \(T(n)=aT(n/4)+\Theta(n^2)\)，要比 Strassen 快需 \(\log_4a<\lg7\)，即 \(a<4^{\lg 7}=49\)，最大整数 \(a=48\)。练习 4.5-5 给出"满足情况 3 除正则条件外所有条件"的例子：\(a=1\)、\(b=2\)、\(f(n)=n(2-\cos n)\)。

情况 2 的扩展

练习 4.6-2 证明：若 \(f(n)=\Theta(n^{\log_ba}\lg^kn)\)（\(k\ge0\)），则

这个扩展很实用。\(2T(n/2)+n\lg n\) 属于 \(k=1\)，解为 \(\Theta(n\lg^2n)\)；练习 4.5-4 的 \(4T(n/2)+n^2\lg n\) 同样不能直接用主定理，但由扩展得 \(\Theta(n^2\lg^2n)\)。

练习 4.6-3 还指出情况 3 的陈述是"过度"的：正则条件 \(af(n/b)\le cf(n)\)（\(c<1\)）本身就蕴含存在 \(\epsilon>0\) 使 \(f(n)=\Omega(n^{\log_ba+\epsilon})\)。

4.6 ★ 主定理的证明

应用主定理不需要理解证明，但证明的结构就是递归树，把三种情况为什么成立讲得很清楚。证明分两部分：先假设 \(n\) 是 \(b\) 的精确幂（\(n=1,b,b^2,\ldots\)），得到全部直觉；再推广到所有整数，处理取整。

警告。 对只在 \(b\) 的幂上定义的函数使用渐近记号是一种滥用，可能得出错误结论。例如在 \(n\) 为 2 的幂时证明了 \(T(n)=O(n)\)，并不能保证对所有 \(n\) 都成立：若 \(T(n)=n\)（\(n=1,2,4,8,\ldots\)），而其余 \(n\) 上 \(T(n)=n^2\)，对所有 \(n\) 的最好上界是 \(O(n^2)\)。

精确幂情形

引理 4.2 设 \(a\ge1\)、\(b>1\)，\(f(n)\) 是定义在 \(b\) 的精确幂上的非负函数，\(T(1)=\Theta(1)\)，\(T(n)=aT(n/b)+f(n)\)（\(n=b^i\)，\(i\ge1\)）。则

证明就是画递归树：深度 \(j\) 有 \(a^j\) 个结点，每个代价 \(f(n/b^j)\)；叶子都在深度 \(\log_bn\)，共 \(a^{\log_bn}=n^{\log_ba}\) 个，每个代价 \(\Theta(1)\)。求和项是所有内部结点（分解与合并）的代价，\(\Theta(n^{\log_ba})\) 是所有叶子的代价。

引理 4.3 在同样条件下，\(g(n)=\sum_{j=0}^{\log_bn-1}a^jf(n/b^j)\) 满足：

1. 若 \(f(n)=O(n^{\log_ba-\epsilon})\)，则 \(g(n)=O(n^{\log_ba})\)；
2. 若 \(f(n)=\Theta(n^{\log_ba})\)，则 \(g(n)=\Theta(n^{\log_ba}\lg n)\)；
3. 若对某常数 \(c<1\) 及足够大的 \(n\) 有 \(af(n/b)\le cf(n)\)，则 \(g(n)=\Theta(f(n))\)。

证明的核心是三种几何级数：

• 情况 1：递增级数，末项主导。 把 \(f(n/b^j)=O((n/b^j)^{\log_ba-\epsilon})\) 代入，利用 \(b^{\log_ba}=a\)：

推导拆解：情况 1 那行式子分三步。第一步，把 \(a^j\big(\frac n{b^j}\big)^{\log_ba-\epsilon}\) 拆开：\(=a^j\cdot n^{\log_ba-\epsilon}\cdot\frac{1}{(b^j)^{\log_ba}}\cdot(b^j)^{\epsilon}\)。第二步，用 \(b^{\log_ba}=a\) 得 \((b^j)^{\log_ba}=a^j\)，与前面的 \(a^j\) 约掉，只剩 \(n^{\log_ba-\epsilon}(b^\epsilon)^j\)。第三步，对 \(j=0,\dots,\log_bn-1\) 求公比为 \(b^\epsilon>1\) 的几何级数和，\(=\frac{(b^\epsilon)^{\log_bn}-1}{b^\epsilon-1}=\frac{n^\epsilon-1}{b^\epsilon-1}\)，乘回去得到 \(\frac{n^{\log_ba}-n^{\log_ba-\epsilon}}{b^\epsilon-1}=O(n^{\log_ba})\)。公比大于 1，级数由最后一项（最靠近叶子的那层）主导，这就是"叶子主导"的严格版本。

• 情况 2：每项相同。 代入 \(f(n/b^j)=\Theta((n/b^j)^{\log_ba})\)，每项都等于 \(n^{\log_ba}\)，共 \(\log_bn\) 项，得 \(\Theta(n^{\log_ba}\lg n)\)。

• 情况 3：递减级数，首项主导。 \(f(n)\) 本身是求和的一项且各项非负，所以 \(g(n)=\Omega(f(n))\)。把正则条件改写为 \(f(n/b)\le(c/a)f(n)\)，迭代 \(j\) 次得 \(a^jf(n/b^j)\le c^jf(n)\)（只有常数个参数很小的项可能不满足，它们合计 \(O(1)\)）。于是

引理 4.4（精确幂版主定理） 把引理 4.3 代入 (4.21)：情况 1 为 \(\Theta(n^{\log_ba})+O(n^{\log_ba})\)；情况 2 为 \(\Theta(n^{\log_ba})+\Theta(n^{\log_ba}\lg n)\)；情况 3 为 \(\Theta(n^{\log_ba})+\Theta(f(n))=\Theta(f(n))\)，因为 \(f(n)=\Omega(n^{\log_ba+\epsilon})\)。三种情况分别对应：总代价由叶子主导、均匀分布在各层、由根主导。

推广到取整

对 \(T(n)=aT(\lceil n/b\rceil)+f(n)\) 求下界、对 \(T(n)=aT(\lfloor n/b\rfloor)+f(n)\) 求上界都是常规的（分别用 \(\lceil n/b\rceil\ge n/b\) 与 \(\lfloor n/b\rfloor\le n/b\)）。难的是另外两个方向，原书只证明向上取整的上界。递归调用的参数序列是 \(n_0=n\)，\(n_j=\lceil n_{j-1}/b\rceil\)。由 \(\lceil x\rceil\le x+1\) 反复展开：

取 \(j=\lfloor\log_bn\rfloor\)，得 \(n_j<b+\frac b{b-1}=O(1)\)，即深度 \(\lfloor\log_bn\rfloor\) 处问题规模已是常数。于是

与 (4.21) 几乎相同。剩下的工作是证明 \(f(n_j)\) 与 \(f(n/b^j)\) 只差常数倍。以情况 2 为例，由于 \(b^j/n\le1\)，

此后与精确幂情形相同。情况 1 类似但代数更繁，情况 3 只需正则条件对 \(\lceil n/b\rceil\) 成立。练习 4.6-1 指出，\(b\) 为正整数时有简单的精确表达式 \(n_j=\lceil n/b^j\rceil\)（用第 03 章的取整恒等式）。

4.7 思考题选讲与更一般的方法

递归式速查（思考题 4-1、4-3）

\(3T(n/3)+n/\lg n\) 的推导值得一看：深度 \(j\) 的层代价是 \(3^j\cdot\frac{n/3^j}{\lg(n/3^j)}=\frac{n}{\lg n-j\lg3}\)，对 \(j\) 求和相当于 \(n\) 乘以一个调和级数的片段，得到 \(\Theta(n\lg\lg n)\)。

斐波那契数与生成函数（思考题 4-4）

定义生成函数 \(\mathcal F(z)=\sum_{i\ge0}F_iz^i=z+z^2+2z^3+3z^4+5z^5+\cdots\)。由递推关系得 \(\mathcal F(z)=z+z\mathcal F(z)+z^2\mathcal F(z)\)，所以

比较系数就得到第 03 章的闭式 \(F_i=(\phi^i-\hat\phi^i)/\sqrt5\)。生成函数是求解线性递推的通用方法，由 De Moivre 引入。

芯片检测（思考题 4-5）

\(n\) 片芯片两两互测，好芯片如实报告，坏芯片的报告不可信。若坏芯片至少占一半，它们可以合谋，任何基于两两测试的策略都无法确定好芯片。若好芯片超过一半：两两配对测试，凡互报"都好"的对只留一片，其余丢弃，这样 \(\lfloor n/2\rfloor\) 次测试就把问题规模减到约一半，且好芯片仍过半。递归式 \(T(n)\le T(\lceil n/2\rceil)+\lfloor n/2\rfloor\)，解为 \(\Theta(n)\)。找到一片好芯片后，再用它测试其余所有芯片。

Monge 阵列（思考题 4-6）

\(m\times n\) 阵列 \(A\) 若对所有 \(i<k\)、\(j<l\) 满足 \(A[i,j]+A[k,l]\le A[i,l]+A[k,j]\)，称为 Monge 阵列：任取两行两列，左上加右下不超过右上加左下。要点：

• 只需检查所有相邻的 \(2\times2\) 子块（对行、列分别归纳）。
• 原书给出的 5 行 4 列非 Monge 阵列 \([37,23,22,32]\)、\([21,6,7,10]\)、\([53,34,30,31]\)、\([32,13,9,6]\)、\([43,21,15,8]\)，违规处在第 1–2 行、第 2–3 列：\(23+7>22+6\)。把 \(A[2,3]=7\) 改为 5，或把 \(A[1,3]=22\) 改为 24，都能使之成为 Monge 阵列（已用程序逐一检查相邻 \(2\times2\) 块验证）。
• 令 \(f(i)\) 为第 \(i\) 行最左最小元素所在列，则 \(f(1)\le f(2)\le\cdots\le f(m)\)。原书 7 行 5 列的例子中 \(f=(1,3,3,3,5,5,5)\)。
• 利用这种单调性，可以只递归求偶数行的 \(f\)，再在相邻两个偶数行的 \(f\) 之间搜索奇数行，\(T(m)=T(m/2)+O(m+n)\)，总计 \(O(m+n\lg m)\)。

Monge 性质在动态规划加速中经常出现（四边形不等式、SMAWK 算法），某些含交易成本的最优执行、分段回归问题可以借此从 \(O(n^2)\) 降下来。

Akra–Bazzi 方法

主方法只适用于子问题规模相等的情况。Akra–Bazzi 方法（Leighton 修改版）可以解更一般的

其中 \(f\) 满足一个多项式增长条件（例如 \(f(x)=x^\alpha\lg^\beta x\) 都满足）。先找唯一实数 \(p\) 使 \(\sum_{i=1}^ka_ib_i^p=1\)，则

例：\(T(n)=T(n/3)+T(2n/3)+n\)，由 \((1/3)^p+(2/3)^p=1\) 得 \(p=1\)，积分 \(\int_1^n\frac{u}{u^2}du=\ln n\)，所以 \(T(n)=\Theta(n\lg n)\)，与递归树的结论一致。它比主方法难用，但能处理子问题大小差别很大的分割。需要时查原书第 4 章章末注记（PDF p.133–134）。

量化实战：验证递归式，分析递归二分配权

数值验证 \(\Theta\) 界

\(\Theta\) 的含义是"比值被夹在两个正常数之间"，不要求比值收敛。下面直接按递归式（含向下取整、\(n<4\) 时 \(T(n)=1\)）算出 \(T(n)\)，在 \(10^4\) 到 \(10^9\) 之间取 60 个点，看 \(T(n)/g(n)\) 的范围。

import math
from functools import lru_cache
import numpy as np

# 1) 数值求解递归式，检验主定理给出的阶：比值 T(n)/g(n) 应被夹在两个正常数之间
cases = {
    "2T(n/2)+n      -> n lg n":    (lambda T, n: 2*T(n//2) + n,          lambda n: n*math.log2(n)),
    "9T(n/3)+n      -> n^2":       (lambda T, n: 9*T(n//3) + n,          lambda n: n**2),
    "3T(n/4)+n lg n -> n lg n":    (lambda T, n: 3*T(n//4) + n*math.log2(n), lambda n: n*math.log2(n)),
    "7T(n/2)+n^2    -> n^lg7":     (lambda T, n: 7*T(n//2) + n*n,        lambda n: n**math.log2(7)),
    "2T(n/2)+n lg n -> n lg^2 n":  (lambda T, n: 2*T(n//2) + n*math.log2(n), lambda n: n*math.log2(n)**2),
    "T(n/3)+T(2n/3)+n -> n lg n":  (lambda T, n: T(n//3) + T(2*n//3) + n, lambda n: n*math.log2(n)),
}
for name, (rec, g) in cases.items():
    @lru_cache(maxsize=None)
    def T(n, rec=rec):
        return 1 if n < 4 else rec(T, n)
    ns = np.unique(np.geomspace(1e4, 1e9, 60).astype(np.int64))
    ratios = np.array([T(int(n)) / g(n) for n in ns])
    print(f"{name:28s} 比值区间 [{ratios.min():.3f}, {ratios.max():.3f}]  n=1e9 时 {ratios[-1]:.3f}")

输出：

2T(n/2)+n      -> n lg n     比值区间 [0.871, 0.976]  n=1e9 时 0.940
9T(n/3)+n      -> n^2        比值区间 [0.186, 0.932]  n=1e9 时 0.331
3T(n/4)+n lg n -> n lg n     比值区间 [2.445, 3.207]  n=1e9 时 3.207
7T(n/2)+n^2    -> n^lg7      比值区间 [0.404, 0.880]  n=1e9 时 0.445
2T(n/2)+n lg n -> n lg^2 n   比值区间 [0.513, 0.527]  n=1e9 时 0.513
T(n/3)+T(2n/3)+n -> n lg n   比值区间 [0.975, 1.040]  n=1e9 时 1.039

白话解释：代码的思路是"老老实实按递归式算出 \(T(n)\)，再除以理论答案 \(g(n)\)，看比值是否稳定"。几处语法：n//2 是整除，对应向下取整 \(\lfloor n/2\rfloor\)；lambda T, n: 2*T(n//2) + n 是一个小函数，把递归式原样写出来；@lru_cache 放在函数定义上方，作用是"记住算过的结果"，同一个 \(T(m)\) 只算一次，否则 \(n=10^9\) 时会重复计算到天荒地老；np.geomspace(1e4, 1e9, 60) 在 \(10^4\) 到 \(10^9\) 之间按等比间隔取 60 个点，相当于在对数坐标上均匀取点。

六个递归式的比值都没有发散，验证了主定理（含情况 2 扩展）与递归树的结论。有两点值得体会：

• 情况 1（叶子主导）的两行比值波动最大（0.19 到 0.93）。原因是向下取整使递归深度和叶子数随 \(n\) 在 \(b\) 的相邻两个幂之间跳动，而叶子正是总代价的主体。比值不收敛，但始终被夹住，这正是 \(\Theta\) 的含义。
• 情况 3 的 \(3T(n/4)+n\lg n\) 比值从 2.4 缓慢升到 3.2。展开可知 \(T(n)\approx\sum_j(3/4)^jn(\lg n-2j)\)，主项是 \(4n\lg n\)，修正项是 \(-O(n)\)，相对误差按 \(1/\lg n\) 缓慢消失，所以比值慢慢逼近 4。低阶项在实际规模下可能并不小，这也是为什么 \(\Theta\) 结论要配合实测。

递归二分配权（HRP）的复杂度

层次风险平价（Hierarchical Risk Parity, HRP）（López de Prado 提出；第 23 章 23.6.3 节从最小生成树出发给出完整实现）分三步：对资产做层次聚类；按聚类树重排资产顺序（准对角化）；对排好序的资产做**递归二分（recursive bisection）**配权。第三步是一个典型的分治：把当前资产组对半分成两组，分别计算两组"组内逆方差组合"的方差 \(V_L\)、\(V_R\)，按 \(\alpha=1-V_L/(V_L+V_R)\) 把权重分给左组、\(1-\alpha\) 分给右组，然后对两组递归。

计算一组 \(m\) 只资产的组合方差 \(w^\top\Sigma w\) 需 \(\Theta(m^2)\)。于是递归二分的代价是

\(a=b=2\)，\(n^{\log_ba}=n\)，\(f(n)=n^2=\Omega(n^{1+1})\)，正则条件 \(2(n/2)^2=\frac12n^2\) 成立（\(c=\frac12\)），属于情况 3，\(T(n)=\Theta(n^2)\)。递归树的图景是根主导：最顶层两次 \(\Theta((n/2)^2)\) 的方差计算就占总代价的一半，各层代价按 \(\frac12\) 递减。

金融直觉：HRP 的递归二分可以想成"自上而下的预算分配"：投委会先把 100% 的风险预算按两大类资产的方差反比切成两份，每一类的负责人再把自己那份按同样规则切给两个子类，一直切到单个资产。每个决策点要算一次组内方差 \(w^\top\Sigma w\)，组内有 \(m\) 只资产就要碰 \(m^2\) 个协方差元素，所以越靠上的决策越贵。第一刀两组各 \(n/2\) 只，花 \(2\cdot(n/2)^2=n^2/2\)；第二刀四组各 \(n/4\) 只，花 \(n^2/4\)；依次减半。总和是 \(n^2(\frac12+\frac14+\cdots)\approx n^2\)，与下面的实测一致。 权重分配公式 \(\alpha=1-\frac{V_L}{V_L+V_R}=\frac{V_R}{V_L+V_R}\)：方差小的一组拿到更多权重，就是两资产情形下的逆方差加权。

代码说明：stack 是一个"待办清单"，每次 pop() 取出一组资产处理，切完后把两半 += 放回清单，这是用循环模拟递归的常见写法；cov[np.ix_(idx, idx)] 取出这组资产对应的子协方差矩阵；ivp @ sub @ ivp 就是 \(w^\top\Sigma w\)。

import numpy as np

# 资产已按聚类顺序排好；每次把一组资产对半分，按两半的方差反比分配权重。
def cluster_var(cov, idx):                 # 组内逆方差组合的方差：Θ(m^2)
    ivp = 1 / np.diag(cov)[idx]; ivp /= ivp.sum()
    sub = cov[np.ix_(idx, idx)]
    return ivp @ sub @ ivp, len(idx) ** 2

def recursive_bisection(cov):
    w = np.ones(cov.shape[0]); ops = 0
    stack = [np.arange(cov.shape[0])]
    while stack:
        idx = stack.pop()
        if len(idx) < 2:
            continue
        L, R = idx[:len(idx)//2], idx[len(idx)//2:]
        vL, oL = cluster_var(cov, L); vR, oR = cluster_var(cov, R)
        ops += oL + oR
        a = 1 - vL / (vL + vR)            # 方差小的一半拿到更多权重
        w[L] *= a; w[R] *= 1 - a
        stack += [L, R]
    return w, ops

rng = np.random.default_rng(3)
for n in (128, 256, 512, 1024):
    F = rng.standard_normal((n, 5)); cov = F @ F.T * 1e-4 + np.diag(rng.uniform(1e-4, 4e-4, n))
    w, ops = recursive_bisection(cov)
    print(f"n={n:5d}  权重和={w.sum():.6f}  运算量={ops:>9,d}  运算量/n^2={ops/n**2:.3f}")

输出：

n=  128  权重和=1.000000  运算量=   16,256  运算量/n^2=0.992
n=  256  权重和=1.000000  运算量=   65,280  运算量/n^2=0.996
n=  512  权重和=1.000000  运算量=  261,632  运算量/n^2=0.998
n= 1024  权重和=1.000000  运算量=1,047,552  运算量/n^2=0.999

运算量与 \(n^2\) 之比趋于 1。精确地说，第 \(j\) 层有 \(2^{j+1}\) 个大小为 \(n/2^{j+1}\) 的组，代价 \(2^{j+1}(n/2^{j+1})^2=n^2/2^{j+1}\)，对 \(j\) 求和得 \(n^2(1-1/n)\)，与输出吻合。权重和恒为 1，因为每次只是把父组的权重按 \(\alpha\) 与 \(1-\alpha\) 拆开。

这个分析有实际意义：HRP 第一步的层次聚类通常是 \(O(n^2\lg n)\) 或 \(O(n^2)\)（取决于实现），协方差估计是 \(O(n^2T)\)，所以递归二分本身不是瓶颈；它避免了均值方差优化中 \(O(n^3)\) 的矩阵求逆，这是 HRP 在大资产池上计算更稳、更快的原因之一。

其他可用递归式分析的量化算法。

• 多尺度分析（如对收益序列做二进小波分解）：每层长度减半、每层线性，\(T(n)=T(n/2)+\Theta(n)=\Theta(n)\)，情况 3。
• 线段树上的区间查询（区间最大值、区间和），建树 \(T(n)=2T(n/2)+\Theta(1)=\Theta(n)\)，情况 1。
• 递归计算 Kendall \(\tau\)（第 01 章）\(T(n)=2T(n/2)+\Theta(n)=\Theta(n\lg n)\)，情况 2。

本章小结

求解递归式有三种方法。代入法先猜后证，要证明归纳假设的精确形式，必要时减去低阶项、调整 \(n_0\) 或替换变量。递归树逐层求和，最适合产生猜测：各层代价递减时根主导，递增时叶子主导，相等时乘以层数；任何常数比例的分割都给出 \(\Theta(n\lg n)\)。主方法比较 \(f(n)\) 与叶子数 \(n^{\log_ba}\)：叶子多项式地多，解为 \(\Theta(n^{\log_ba})\)；同阶，乘以 \(\lg n\)；\(f\) 多项式地大且满足正则条件，解为 \(\Theta(f(n))\)。三种情况之间有空隙，\(f(n)=\Theta(n^{\log_ba}\lg^kn)\) 时可用扩展得 \(\Theta(n^{\log_ba}\lg^{k+1}n)\)，不等分割可用递归树或 Akra–Bazzi。主定理的证明就是递归树加三种几何级数，取整只改变常数。

练习

基础

1. 用主方法求下列递归式的紧确界：\(2T(n/4)+1\)；\(2T(n/4)+\sqrt n\)；\(2T(n/4)+n\)；\(2T(n/4)+n^2\)。 答案：\(\Theta(\sqrt n)\)；\(\Theta(\sqrt n\lg n)\)；\(\Theta(n)\)；\(\Theta(n^2)\)。
2. 用代入法证明 \(T(n)=T(n-1)+n\) 的解为 \(O(n^2)\)。
3. 用代入法证明 \(T(n)=T(\lceil n/2\rceil)+1\) 的解为 \(O(\lg n)\)。 提示：直接假设 \(T(n)\le c\lg n\) 会因向上取整卡住，可改证 \(T(n)\le c\lg(n-2)\) 并适当选取 \(n_0\)。
4. 证明 \(T(n)=2T(\lfloor n/2\rfloor)+n\) 也是 \(\Omega(n\lg n)\)，从而为 \(\Theta(n\lg n)\)。
5. 用主方法证明二分查找 \(T(n)=T(n/2)+\Theta(1)\) 的解为 \(\Theta(\lg n)\)。
6. 用递归树求 \(T(n)=3T(\lfloor n/2\rfloor)+n\) 的渐近上界，并用代入法验证。 答案：\(\Theta(n^{\lg3})\)；代入时用 \(cn^{\lg3}-dn\)。

进阶

7. 用变量替换求 \(T(n)=3T(\sqrt n)+\lg n\)。 答案：\(\Theta((\lg n)^{\lg3})\)。
8. \(T(n)=4T(n/2)+n^2\lg n\) 能否直接用主方法？给出渐近紧确界。 答案：不能（落入情况 2 与 3 之间的空隙）；由情况 2 扩展得 \(\Theta(n^2\lg^2n)\)。
9. 求使 \(T(n)=aT(n/4)+\Theta(n^2)\) 渐近快于 Strassen 的最大整数 \(a\)。 答案：\(a=48\)。
10. 量化应用：某因子回测框架对 \(n\) 只股票做递归分组，每层把股票按某个特征对半分，每组计算组内相关矩阵（\(\Theta(m^2)\)）并做一次排序（\(\Theta(m\lg m)\)），分到单只股票为止。写出递归式并求解。若把相关矩阵换成只计算组内均值（\(\Theta(m)\)），排序保留，结果如何？ 答案：\(T(n)=2T(n/2)+\Theta(n^2)=\Theta(n^2)\)（情况 3）；改后 \(T(n)=2T(n/2)+\Theta(n\lg n)=\Theta(n\lg^2n)\)（情况 2 扩展）。

原书推荐习题：4.3-7、4.3-8（减低阶项的代入法）；4.4-9（任意常数比例分割，为快速排序分析打基础）；4.5-1、思考题 4-1、4-3（熟练使用主方法并识别不适用情形）；4.6-2（情况 2 扩展，很实用）；思考题 4-5（芯片检测）、4-6（Monge 阵列，与动态规划加速相关）。

原书对照