主定理的进阶：Akra–Bazzi 定理

之前我们讲了主定理，用来解决： \( T(n)=aT(n/b)+f(n) \) 的复杂度

但现实里的递归，往往没有这么整齐。比如每个子问题的规模不同：

这时候，主定理就不能直接用了。这篇我们讲一个更强的工具：Akra–Bazzi 定理。

主定理的扩展

很多算法的递归是这样的：

或者：

这些递归的特点是：子问题规模不同、递归分支不均匀。主定理无法直接套。这时候就需要 Akra–Bazzi 定理。

Akra–Bazzi 定理处理什么

Akra–Bazzi 定理处理的是：

其中：

• \(a_i\) 表示第 \(i\) 类子问题有多少个
• \(n/b_i\) 表示第 \(i\) 类子问题的规模
• \(f(n)\) 表示递归之外的额外工作

它是主定理的扩展。主定理是它的特殊情况。

计算核心：先求一个 \(p\)

Akra–Bazzi 的第一步，是找到 \(p\)，使得：

这个 \(p\) 可以理解为递归结构本身的增长指数。为什么？假设 \(T(n)\) 大概像 \(n^p\)，代入递归：

整理得：

所以必须有：

这就是 Akra–Bazzi 定理的灵魂。

结论

求出 \(p\) 之后，有：

这个公式可以拆成两部分看：

• \(n^p\)：递归结构本身的复杂度
• 积分：每一层额外工作 \(f(n)\) 的累计影响

因此，使用 Akra–Bazzi 定理计算复杂度分为三步：

第一步，解方程求出 p：

第二步，计算积分：

第三步，乘回 \(n^p\)：

例子

主定理无法处理的递归

考虑：

这里有两个子问题，规模分别是 \(n/2\) 和 \(n/3\)。

所以：\( (1/2)^p+(1/3)^p=1 \)，这个方程的解大约是：\( p\approx 0.79 \)

又因为 \(f(n)=n\)，所以：\( T(n)=\Theta\left(n^p\left(1+\int_1^n \frac{u}{u^{p+1}}du\right)\right) \)

积分部分为：\( \int_1^n u^{-p}du=\Theta(n^{1-p}) \)

因此：\( T(n)=\Theta(n^p\cdot n^{1-p})=\Theta(n) \)

不均匀分治

快速排序不可能每次都选到最中间的枢纽。假设快速排序每次都把数组分成 \(1/4\) 和 \(3/4\) 两部分。递归为：

求 \(p\)：\( (1/4)^p+(3/4)^p=1 \)。显然 \(p=1\)。

于是：\( T(n)=\Theta\left(n\left(1+\int_1^n \frac{u}{u^2}du\right)\right) \)

最终 \( T(n)=\Theta(n\log n) \)

这和快速排序的直觉一致：只要划分不是极端不平衡，快速排序仍然是 \(O(n\log n)\)。事实上，只要每层总工作量是线性的，并且问题按固定比例缩小，总复杂度通常还是 \(n\log n\) 级别。

BFPRT 选择算法

BFPRT，也就是线性时间选择算法，会出现类似递归：

其中：

• \(T(n/5)\) 来自递归寻找中位数的中位数
• \(T(7n/10)\) 来自递归处理剩下的一侧
• \(O(n)\) 来自分组、找中位数和 partition

求 \( (1/5)^p+(7/10)^p=1 \)

由于当 \(p=1\) 时：\( 1/5+7/10=9/10<1 \)。所以真正的 \(p<1\)。

代入 Akra–Bazzi 公式后，这就和例子一完全一样了。最终 \( T(n)=\Theta(n) \)

递归结构本身占主导

考虑：

求 \(p\)：\( 2(1/2)^p+(1/4)^p=1 \)

当 \(p=1\) 时：\( 2\cdot \frac12+\frac14=\frac54>1 \)

当 \(p=2\) 时：\( 2\cdot \frac14+\frac1{16}=\frac9{16}<1 \)

所以：