主定理的进阶：Akra–Bazzi 定理
主定理的扩展
很多算法的递归是这样的：
T(n)=T(n/3)+T(2n/3)+O(n)T(n)=T(n/3)+T(2n/3)+O(n)
或者：
T(n)=T(n/5)+T(7n/10)+O(n)T(n)=T(n/5)+T(7n/10)+O(n)
这些递归的特点是：子问题规模不同、递归分支不均匀。主定理无法直接套。这时候就需要 Akra–Bazzi 定理。
Akra–Bazzi 定理处理什么
Akra–Bazzi 定理处理的是：
T(n)=f(n)+∑i=1kaiT(n/bi)T(n)=f(n)+i=1∑kaiT(n/bi)
其中：
- aiai 表示第 ii 类子问题有多少个
- n/bin/bi 表示第 ii 类子问题的规模
- f(n)f(n) 表示递归之外的额外工作
它是主定理的扩展。主定理是它的特殊情况。
计算核心：先求一个 pp
Akra–Bazzi 的第一步，是找到 pp，使得：
∑i=1kaibi−p=1i=1∑kaibi−p=1
这个 pp 可以理解为递归结构本身的增长指数。为什么？假设 T(n)T(n) 大概像 npnp，代入递归：
np≈∑i=1kai(n/bi)pnp≈i=1∑kai(n/bi)p
整理得：
np≈np∑i=1kaibi−pnp≈npi=1∑kaibi−p
所以必须有：
∑i=1kaibi−p=1i=1∑kaibi−p=1
这就是 Akra–Bazzi 定理的灵魂。
结论
求出 pp 之后，有：
T(n)=Θ(np(1+∫1nf(u)up+1du))T(n)=Θ(np(1+∫1nup+1f(u)du))
这个公式可以拆成两部分看：
- npnp：递归结构本身的复杂度
- 积分：每一层额外工作 f(n)f(n) 的累计影响
因此，使用 Akra–Bazzi 定理计算复杂度分为三步：
第一步，解方程求出 p：
∑i=1kaibi−p=1i=1∑kaibi−p=1
第二步，计算积分：
∫1nf(u)up+1du∫1nup+1f(u)du
第三步，乘回 npnp：
T(n)=Θ(np(1+∫1nf(u)up+1du))T(n)=Θ(np(1+∫1nup+1f(u)du))
例子
主定理无法处理的递归
考虑：
T(n)=T(n/2)+T(n/3)+nT(n)=T(n/2)+T(n/3)+n
这里有两个子问题，规模分别是 n/2n/2 和 n/3n/3。
所以：(1/2)p+(1/3)p=1(1/2)p+(1/3)p=1，这个方程的解大约是：p≈0.79p≈0.79
又因为 f(n)=nf(n)=n，所以：T(n)=Θ(np(1+∫1nuup+1du))T(n)=Θ(np(1+∫1nup+1udu))
积分部分为：∫1nu−pdu=Θ(n1−p)∫1nu−pdu=Θ(n1−p)
因此：T(n)=Θ(np⋅n1−p)=Θ(n)T(n)=Θ(np⋅n1−p)=Θ(n)
不均匀分治
快速排序不可能每次都选到最中间的枢纽。假设快速排序每次都把数组分成 1/41/4 和 3/43/4 两部分。递归为：
T(n)=T(n/4)+T(3n/4)+O(n)T(n)=T(n/4)+T(3n/4)+O(n)
求 pp：(1/4)p+(3/4)p=1(1/4)p+(3/4)p=1。显然 p=1p=1。
于是：T(n)=Θ(n(1+∫1nuu2du))T(n)=Θ(n(1+∫1nu2udu))
最终 T(n)=Θ(nlogn)T(n)=Θ(nlogn)
这和快速排序的直觉一致：只要划分不是极端不平衡，快速排序仍然是 O(nlogn)O(nlogn)。事实上，只要每层总工作量是线性的，并且问题按固定比例缩小，总复杂度通常还是 nlognnlogn 级别。
BFPRT 选择算法
BFPRT，也就是线性时间选择算法，会出现类似递归：
T(n)=T(n/5)+T(7n/10)+O(n)T(n)=T(n/5)+T(7n/10)+O(n)
其中：
- T(n/5)T(n/5) 来自递归寻找中位数的中位数
- T(7n/10)T(7n/10) 来自递归处理剩下的一侧
- O(n)O(n) 来自分组、找中位数和 partition
求 (1/5)p+(7/10)p=1(1/5)p+(7/10)p=1
由于当 p=1p=1 时：1/5+7/10=9/10<11/5+7/10=9/10<1。所以真正的 p<1p<1。
代入 Akra–Bazzi 公式后，这就和例子一完全一样了。最终 T(n)=Θ(n)T(n)=Θ(n)
递归结构本身占主导
考虑：
T(n)=2T(n/2)+T(n/4)+O(n)T(n)=2T(n/2)+T(n/4)+O(n)
求 pp：2(1/2)p+(1/4)p=12(1/2)p+(1/4)p=1
当 p=1p=1 时：2⋅12+14=54>12⋅21+41=45>1
当 p=2p=2 时：2⋅14+116=916<12⋅41+161=169<1
所以：
1<p<21<p<2
这里递归结构本身增长得比 nn 更快。
因此：T(n)=Θ(np)T(n)=Θ(np)。其中 pp 是方程 2(1/2)p+(1/4)p=12(1/2)p+(1/4)p=1 的解。
