第04章 分治策略 — 章节汇总

章节概览

本章是第2章分治法的深化，聚焦于分治策略的两大应用方向——矩阵乘法优化和递归关系式求解。前半部分（4.14.2）以矩阵乘法为案例，展示如何通过分治思想将朴素算法的 $\Theta (n^3)$ 降低到 $\Theta (n^{2.81})$；后半部分（4.34.7）系统介绍三种求解递归关系式的方法——代入法、递归树法和主定理，并给出主定理的严格证明及其推广形式 Akra-Bazzi 方法。

---

4.1~4.2 矩阵乘法与 Strassen 算法

小节	核心主题	关键结论
4.1 矩阵乘法	标准矩阵乘法与分治矩阵乘法	朴素算法 $\Theta (n^3)$；分治 8 次递归乘法仍为 $\Theta (n^3)$
4.2 Strassen算法	Strassen 矩阵乘法	仅需 7 次递归乘法，复杂度降至 $\Theta (n^{\lg 7})=\Theta (n^{2.81})$

核心思路：将 $n\times n$ 矩阵划分为 4 个 $(n/2)\times (n/2)$ 子矩阵，通过巧妙组合子矩阵的加减运算，将递归乘法次数从 8 次减少到 7 次。虽然每次递归增加了常数次矩阵加减（$\Theta (n^2)$），但乘法次数的减少在渐近意义上带来了显著提升。

---

4.3~4.4 递归关系式求解方法（上）

小节	核心主题	关键结论
4.3 代入法	猜测 + 数学归纳证明	先猜测解的形式，再用归纳法严格验证；技巧：减去低阶项
4.4 递归树法	逐层展开递归树求和	直观展示递归的层次结构，适合几何级数型递归

代入法要点：

• 猜测上界时，先减去低阶项（subtract a lower-order term），避免归纳假设过强导致证明失败
• 猜测下界时，先加上低阶项（add a lower-order term）
• 证明过程中可能需要调整常数因子

递归树法要点：

• 每一层的代价求和，形成几何级数
• 适用于 $T(n)=aT(n/b)+f(n)$ 形式的递归
• 树的深度为 ${\log }_{b}n$，叶子数为 $a^{{\log }_{b}n}=n^{{\log }_{b}a}$

---

4.5~4.7 递归关系式求解方法（下）与推广

小节	核心主题	关键结论
4.5 主定理	主定理三种情形	根据多项式增长比较 $f(n)$ 与 $n^{{\log }_{b}a}$，分三种情形求解
4.6 连续主定理的证明	主定理的严格证明	利用递归树 + 上下界夹逼，核心引理证明几何级数的收敛性
4.7 Akra-Bazzi递归	广义主定理	处理 $T(n)={\sum }_{i=1}^k{a}_{i}T(n/b_i)+f(n)$ 形式，解由积分给出

主定理三种情形（$T(n)=aT(n/b)+f(n)$，$a\ge 1,b>1$）：

1. 情形一：$f(n)=O(n^{{\log }_{b}a-ϵ})$，则 $T(n)=\Theta (n^{{\log }_{b}a})$（递归代价主导）
2. 情形二：$f(n)=\Theta (n^{{\log }_{b}a}{\lg }^{k}n)$，则 $T(n)=\Theta (n^{{\log }_{b}a}{\lg }^{k+1}n)$（两代价平衡）
3. 情形三：$f(n)=\Omega (n^{{\log }_{b}a+ϵ})$ 且满足正则性条件 $af(n/b)\le cf(n)$，则 $T(n)=\Theta (f(n))$（根代价主导）

Akra-Bazzi 方法：当递归中子问题大小不同（$n/b_i$）时，找到满足 ${\sum }_{i=1}^k{a}_i/b_i^p=1$ 的 $p$，则 $T(n)=\Theta \left(n^p\left(1+{\int }_1^n\frac{f(u)}{u^{p+1}}du\right)\right)$。

---

跨章节关联

关联章节	关联内容
第2章	分治法范式、归并排序的递归关系式 $T(n)=2T(n/2)+\Theta (n)$ 是主定理情形二的典型实例
5.1 概率分析	第5章将使用主定理分析随机化算法的期望运行时间

---

笔记索引

小节	笔记链接
4.1	4.1 矩阵乘法
4.2	4.2 Strassen算法
4.3	4.3 代入法
4.4	4.4 递归树法
4.5	4.5 主定理
4.6	4.6 连续主定理的证明
4.7	4.7 Akra-Bazzi递归

分治策略