Akra–Bazzi 定理
Jayun
·
·
个人记录
Akra–Bazzi 定理
前言
主定理狗都不学！，我写本文的起因是这篇帖子和这篇。
由于 Akra–Bazzi 定理涉及到积分相关知识，所以还是建议先去学习主定理。
主定理有很多情况不适用，上一篇日报结尾也提到了另一种时间复杂度计算方法——Akra–Bazzi 定理，但因为当时我太菜了，所以不会。
主定理的局限性
主定理只适用于：
T(n)=aT(\frac{n}{b})+f(n)
类型的递归式，并且 f(n) 必须要和 n^{\log_ba} 有 n^\epsilon 的差距或有 \log 的差距 ，下面式子就不适用了：
T(n)=4T(\frac{n}{2})+\frac{n^2}{\log n}
T(n)=3T(\frac{n}{2})+4T(\frac{n}{4})+n
这个时候就可以用递归树解决，或者用 Akra–Bazzi 定理。
Akra–Bazzi 定理介绍
Akra–Bazzi 定理适用于递归公式
\Theta(1) & x<x_0\\
g(x)+\sum_{i=1}^{k}a_iT(b_ix+h_i(x)) & x\geq x_0
\end{matrix}\right.
其中：
求出 p 使得 \sum_{i=1}^{k}a_ib_i^p=1，那么就有：
T(x)\in\Theta\left(x^p\left(1+\int_{1}^x\frac{g(u)}{u^{p+1}}du\right)\right)
例子
例一
T(n)=3T(\frac{n}{2})+4T(\frac{n}{4})+n
这时 a=\{3,4\},b=\left\{\frac12,\frac14\right\}，使 \frac{3}{2^p}+\frac{4}{4^p}=1，即 p=2。
&=\Theta\left(n^2\left(1+\frac{n-1}{n}\right)\right) \\
&=\Theta\left(n^2\cdot\frac{2n-1}{n}\right) \\
&=\Theta\left(2n^2-n\right) \\
&=\Theta\left(n^2\right)\end{aligned}
例二
T(n)=4T(\frac{n}{2})+\frac{n^2}{\log n}
这时 a=4,b=\dfrac{1}{2}，使 \frac{4}{2^p}=1，即 p=2。
\begin{aligned}T(n)&=\Theta\left(n^2\left(1+\int_1^n\frac{\frac{x^2}{\log x}}{x^3}dx\right)\right) \\ &=\Theta\left(n^2\left(1+\int_1^n\frac{1}{x\log x}dx\right)\right) \\ &=\Theta\left(n^2\left(1+\log\log n\right)\right) \\ &=\Theta\left(n^2\log\log n\right)\end{aligned}
Akra–Bazzi 定理证明
我不会，长大之后再学（
参考文献
Akra–Bazzi method - Wikipedia