计算时间复杂度

,

前言

首先，注意几个符号：

符号 $\Theta$ 既是上界也是下界。

符号 $O$ 表示上界。

符号 $\Omega$ 表示下界。

Master 定理

又称为主定理，具体内容如下：

$T(n)=aT(n/b)+f(n)$，则：

  1. $f(n)<O(n^{\log_b^a} )\Longrightarrow T(n)=\Theta(n^)$。

  2. $f(n)=\Theta(n^{\log_b^a}\log^kn) \Longrightarrow T(n)=\Theta(n^{\log_b^a}\log^{k+1}n)$

  3. 假设存在常数 $ϵ>0$ ，有 $f(n)=Ω(n^{log_b^a+ϵ})$，同时存在常数 $c<1$ 以及充分大的 $n$ 满足 $af(n/b)≤cf(n)$ ,那么 $T(n)=Θ(f(n))$。

注意第三个情况，有一些情况是不可以用的，如：

$T(n)=4T(n/2)+\frac{n^2}{\log n}$

正确答案是 $\Theta(n^2\log\log n)$。

XXX 定理

在算法导论上看到的，定理名字忘记了，内容如下：

$T(n)=\sum\limits a_iT(n\cdot b_i)+f(n)$

其中 $0<b_i<1$。

令实数 $p$ 为 $\sum\limits a_ib_i^p=1$ 的解，可以证明是存在解的。

$$T(n)=\Theta(n^p(1+\int_1^n \dfrac{f(x)}{x^{p+1}}dx))$$

用法比主定理更广，也没有很多的限制。

例如：

$T(n)=T(\dfrac{n}{3})+2T(\dfrac{2n}{3})+O(n\log n)$

此时 $p=2$ ,$T(n)=\Theta(n^2)$。

万金油：数学归纳法

猜测 $T(n)=g(n)$，然后瞎搞。

可能有用的 link