之前我们讲了主定理，用来解决： \( T(n)=aT(n/b)+f(n) \) 的复杂度
但现实里的递归，往往没有这么整齐。比如每个子问题的规模不同：
\[T(n)=T(n/2)+T(n/3)+n \]
这时候，主定理就不能直接用了。这篇我们讲一个更强的工具：Akra–Bazzi 定理。
很多算法的递归是这样的：
\[T(n)=T(n/3)+T(2n/3)+O(n) \]
或者：
\[T(n)=T(n/5)+T(7n/10)+O(n) \]
这些递归的特点是：子问题规模不同、递归分支不均匀。主定理无法直接套。这时候就需要 Akra–Bazzi 定理。
Akra–Bazzi 定理处理的是：
\[T(n)=f(n)+\sum_{i=1}^{k} a_iT(n/b_i) \]
其中：
它是主定理的扩展。主定理是它的特殊情况。
Akra–Bazzi 的第一步，是找到 \(p\)，使得：
\[\sum_{i=1}^{k} a_i b_i^{-p}=1 \]
这个 \(p\) 可以理解为递归结构本身的增长指数。为什么？假设 \(T(n)\) 大概像 \(n^p\)，代入递归：
\[n^p \approx \sum_{i=1}^{k} a_i(n/b_i)^p \]
整理得：
\[n^p \approx n^p\sum_{i=1}^{k} a_i b_i^{-p} \]
所以必须有：
\[\sum_{i=1}^{k} a_i b_i^{-p}=1 \]
这就是 Akra–Bazzi 定理的灵魂。
求出 \(p\) 之后，有：
\[T(n)=\Theta\left(n^p\left(1+\int_1^n \frac{f(u)}{u^{p+1}}du\right)\right) \]
这个公式可以拆成两部分看：
因此，使用 Akra–Bazzi 定理计算复杂度分为三步：
第一步，解方程求出 p：
\[\sum_{i=1}^{k} a_i b_i^{-p}=1 \]
第二步，计算积分：
\[\int_1^n \frac{f(u)}{u^{p+1}}du \]
第三步，乘回 \(n^p\)：
\[T(n)=\Theta\left(n^p\left(1+\int_1^n \frac{f(u)}{u^{p+1}}du\right)\right) \]
考虑：
\[T(n)=T(n/2)+T(n/3)+n \]
这里有两个子问题，规模分别是 \(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\) 两部分。递归为：
\[T(n)=T(n/4)+T(3n/4)+O(n) \]
求 \(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，也就是线性时间选择算法，会出现类似递归：
\[T(n)=T(n/5)+T(7n/10)+O(n) \]
其中：
求 \( (1/5)^p+(7/10)^p=1 \)
由于当 \(p=1\) 时：\( 1/5+7/10=9/10<1 \)。所以真正的 \(p<1\)。
代入 Akra–Bazzi 公式后，这就和例子一完全一样了。最终 \( T(n)=\Theta(n) \)
考虑：
\[T(n)=2T(n/2)+T(n/4)+O(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 \)
所以：
\[1<p<2 \]
这里递归结构本身增长得比 \(n\) 更快。
因此：\( T(n)=\Theta(n^p) \)。其中 \(p\) 是方程 \( 2(1/2)^p+(1/4)^p=1 \) 的解。
主定理处理：
\[T(n)=aT(n/b)+f(n) \]
这是 Akra–Bazzi 的特殊情况。
此时只有一类子问题，所以方程变成：\( ab^{-p}=1 \)
解得：\( p=\log_b a \)
这正好就是主定理里的关键指数。
所以：
\[\text{主定理}=\text{Akra–Bazzi 在等规模子问题下的特例} \]
Akra–Bazzi 定理要求 \(f(n)\) 不能太奇怪。直观地说，\(f(n)\) 要比较平滑，不能剧烈震荡。就常见的函数来说：
\[f(n)=\Theta(n^\alpha \log^\beta n) \]
都是可以的。但像 \( f(n)=2^n \) 这种就不可用。
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。