4.3 分治递推与主定理：先验证模型，再套结论
算法森林送来几棵外形相似的递归树，希望瞭望塔给出增长速度；你们要先判断它们是否真的属于同一模型。
主定理能快速求一类分治递推，但它不是看到递归就能使用的复杂度计算器。使用前必须确认子问题数量、缩小比例和当前层成本符合模型。
标准模型
主定理处理：
T(n)=aT(n/b)+f(n)其中：
a≥1：子问题个数；b>1：每个子问题的规模缩小为约n/b；f(n)：拆分、合并及其他非递归成本。
比较基准：
n^(log_b a)它近似表示递归树叶子总量带来的成本。
三种常见情形
情形 1：叶子侧占主导
若存在 ε>0：
f(n)=O(n^(log_b a-ε))则：
T(n)=Θ(n^(log_b a))例：
T(n)=8T(n/2)+n²n^(log₂8)=n³，n² 多项式级更小，所以 T(n)=Θ(n³)。
情形 2：各层大致平衡
标准简化版中，若：
f(n)=Θ(n^(log_b a))则：
T(n)=Θ(n^(log_b a) log n)归并排序：
T(n)=2T(n/2)+Θ(n)基准也是 n，所以 Θ(n log n)。
更一般版本可处理额外的对数因子，但使用时要明确采用哪个版本，不能把不同教材的条件混在一起。
情形 3：根部工作占主导
若存在 ε>0：
f(n)=Ω(n^(log_b a+ε))并满足正则条件：存在 c<1，对充分大的 n：
a f(n/b) ≤ c f(n)则：
T(n)=Θ(f(n))例：
T(n)=2T(n/2)+n²基准为 n，n² 多项式级更大，且正则条件成立，所以 Θ(n²)。
正则条件不能省略，它阻止 f(n) 在不同规模间剧烈振荡，使递归子层总工作确实比当前层按固定比例小。
三个典型例子
二分查找
T(n)=T(n/2)+Θ(1)a=1,b=2，基准 n^0=1，属于情形 2：
T(n)=Θ(log n)归并排序
T(n)=2T(n/2)+Θ(n)得到 Θ(n log n)。
Strassen 矩阵乘法
T(n)=7T(n/2)+Θ(n²)基准 n^(log₂7) 约为 n^2.807，大于 n²：
T(n)=Θ(n^(log₂7))渐近优势不等于所有矩阵规模上都更快；常数、缓存和数值稳定性仍需实测。
主定理不适用的递推
T(n)=T(n-1)+n // 子问题不是 n/b
T(n)=T(n/3)+T(2n/3)+n // 子问题大小不相等
T(n)=2T(n/2)+n log n // 取决于使用的主定理版本
T(n)=T(√n)+1 // 缩小形式不同
T(n)=T(n-1)+T(n-2)+1 // Fibonacci 型这些递推可以用展开、递归树、代入、变量替换、特征方程或 Akra–Bazzi 等工具。不能套主定理不等于无法分析。
快速排序尤其需要区分情况：
- 最坏划分：
T(n)=T(n-1)+Θ(n)=Θ(n²)； - 理想平衡：
2T(n/2)+Θ(n)=Θ(n log n)； - 随机或平均分析需要概率模型，不能直接把每次划分假定成一半。
从实现确认递推假设
分析合并排序时，若每层都复制整个数组片段，f(n) 可能仍是线性，但空间和常数不同。若语言切片是视图，成本又不同。建立递推前应确认：
- 子问题是否重叠；
- 切片是复制还是视图；
- 合并是否真的线性；
- 输入是否始终平衡；
- 并行执行时衡量的是总工作还是关键路径；
- 基础阈值和混合算法是否改变小规模行为。
递归、记忆化与动态规划
若子问题重叠，直接递归会反复计算。记忆化按参数缓存结果，把递归调用图从树压成有向无环图。它适合：
- 相同参数确实表示相同子问题；
- 结果不依赖隐藏的可变状态；
- 缓存键有稳定相等语义；
- 状态数量可控。
自底向上动态规划按依赖顺序填表，常能避免递归栈并优化空间。两者求解同一递推时复杂度可能相同，但访问顺序和常数不同。
缓存不是免费的：无界记忆化可能把时间问题换成内存泄漏；并发缓存还涉及重复计算、锁竞争和失败结果是否缓存。
一条实用分析流程
- 选择输入规模
n； - 明确基本情况；
- 数出每个递归子问题的数量和规模；
- 计算当前层非递归工作
f(n)； - 判断子问题是否重叠、是否随机；
- 选择展开、树、主定理或其他方法；
- 用归纳或上下界检查结论；
- 单独分析空间、栈深度和实际成本模型。
完成检查
为二分查找、归并排序、快速排序和一个树遍历分别：
- 写出最好、平均或最坏情况所需假设；
- 建立时间递推；
- 判断主定理是否适用；
- 求渐近界；
- 写出递归深度和额外空间；
- 指出实现中哪项操作若改变，会使递推失效。