今天看到了一个叫做 Akra-Bazzi method 的东西，感觉非常震惊。

对于一个递推式

$T(x)=g(x)+\sum_{i=1}^n a_i T(b_i x+h_i(x))$

其中 $a_i,b_i$ 均为常数，且 $a_i>0,0<b_i<1$，存在常数 $c$ 满足 $g(x)=O(x^c)$，$h_i(x)=O(x/\log^2 x)$. 那么

$T(x)=\Theta\left(x^p\left(1+\int_1^x g(u)/u^{p+1}\ \mathrm{d}u\right)\right)$

其中 $p$ 是 $\sum_{i=1}^n a_i b_i^p=1$ 的解。

下面以这个帖的例 3 为例。

$T(n)=3T(\frac{n}{2})+4T(\frac{n}{4})+n$

首先求 $p$. $3(1/2)^p+4(1/4)^p=1$，容易肉眼解得 $p=2$. 那么

$T(x)=\Theta\left(x^2\left(1+\int_1^x u/u^{p+1}\ \mathrm{d}u\right)\right)=\Theta(x^2(1+1/x))=\Theta(x^2)$

QED.

主要劣势就是计算量太大。