I.主定理适用范围:
\(T(1)=\mathcal{O}(1)\) \(\space \space \space \space \space n=1\)
\(T(n)=a*T(\frac{n}{b})+\mathcal{O}(n^d)\) \(\space \space \space \space \space \space n\geq1\)
II.主定理内容:
当 \(d<\log_b a\) 时,递归时间复杂度为:\(\mathcal{O}(n^{\log_b a})\)
当 \(d=\log_ba\) 时,递归时间复杂度为:\(\mathcal{O}(n^d * \log n)\)
当 \(d>\log_b a\) 时,递归时间复杂度为:\(\mathcal{O}(n^d)\)
III.Akra-Bazzi定理
$Definition: $设 \(g(x)\) 为一定义在非负实数上的函数, \(\{b_k\}\) 为一个含有 \(k\) 项的数列且满足 \(0 < b_i< 1\) ,若存在正常数 \(c_1, c_2\) 使得对任意 \(x \geq 1, 1 \leq i \leq k, u \in [b_i x , x]\) ,均有 \(c_1 g(x) \leq g(u) \leq c_2 g(x)\),则称 \(g(x)\) 满足多项式增长条件
由定义可知,若存在 \(c > 0\) ,使得 \(|g'(x)| \in \mathcal{O}(x^c)\) ,则 \(g(x)\) 满足多项式增长条件。例如,对任意 \(\alpha, \beta \in \mathbb{R} , g(x) = x^{\alpha} \lg^{\beta} x\) 均满足多项式增长条件。
\(Theorem:\)设 \(g(x)\)为一非负函数, $T(x) = $ \(\left\{ \begin{aligned}&\Theta(1)&,&1 \leq x \leq X_0 \\ &\sum_{i = 1}^k a_i T(b_i x) +g(x)&, &n>X_0 \end{aligned}\right.\)
(其中 \(k \geq 1, a_i > 0, 0 < b_i < 1 , X_0\) 满足对任意 \(1 \leq i \leq k\) 有 \(X_0\) \(>\) \(\frac{1}{b_i}\) 且$ X_0> \frac{1}{1-b_i}$ )
若 \(g(x)\) 满足多项式增长条件, $p $为方程 \(\sum_{i = 1}^k a_i b_i^p = 1\) 的实数解,则
\(\begin{aligned} T(x) &= \Theta \left(x^p \left( 1 + \int_1^x \frac{g(u)}{u^{p+1}} du\right)\right) \end{aligned}\)