时间复杂度乱推

引理

$\sum _{i=0} ^ {\log_2n} 2^i =n$（注意这里的等于只是量级上面的等于）

时间复杂度的渐进符号

大 $Θ$ 符号

存在 $c_1,c_2,n_0 > 0$，使得：

$\forall n \ge n_0,0 \le c_1\cdot g(n) \le f(n) \le c_2 \cdot g(n)$

则称：

$f(n)=Θ(g(n))$

简单来说，就是保留对于每个字母来说增长最快的项，增长速度我们有比较直观的感受：

$1 \le \log n \le \log^\alpha n \le \sqrt n \le n$

$\forall \alpha,\beta>0,\exist n_0, \forall n \ge n_0,s.t. \log^\alpha(n)<n^{\beta}$

大 $O$ 符号

只关心上界。

大 $\Omega$ 符号

只关心下界。

小 $o$ 符号

$O$ 符号相当于小于等于号，那么 $o$ 符号就相当于小于号。

小 $\omega$ 符号

$\Omega$ 相当于大于等于号，那么 $\omega$ 就相当于大于号。

推算时间复杂度的方法

画长方形法

例题 1

归并排序时间复杂度 $T(n)=2T(n/2)+O(n)$。

可以画图分析，显然每层都是$n$，有 $\log n$ 层，所以是 $O(n\log n)$。

例题2

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

可以看出只有$\log n$层，但是每层相比于上层都乘了$2$。

总共 $n\sum _{i=0}^{\log n} 2^i = n^2$。

主定理

$T(n) = a T\left(\frac{n}{b}\right)＋f(n)\qquad \forall n > b$

$T(n) = \begin{cases}\Theta(n^{\log_b a}) & f(n) = O(n^{\log_b a-\epsilon}) \\ \Theta(f(n)) & f(n) = \Omega(n^{\log_b a+\epsilon}) \\ \Theta(n^{\log_b a}\log^{k+1} n) & f(n)=\Theta(n^{\log_b a}\log^k n),k\ge 0 \end{cases}$

势能分析

我们设研究对象的状态为 $D$，定义势能函数 $\Phi(D)$，研究一次时间开销（$T_i$）和势能变化（$\Delta\Phi=\Phi(D')-\Phi(D)$）总和的上界 $A_i$：

$T_i -\Delta \Phi \le A_i$

两边求和，得到

$\sum T_i +\Phi_0-\Phi_n \le \sum A_i$

则 ：

$\sum T_i \le \sum A_i + \Phi_n -\Phi_0 \le \sum A_i + \max\{\Phi_n -\Phi_0\}$

例题 3

模拟二进制数的加法。

我们令势能函数 $\Phi (n)$ 代表 $n$ 二进制表示中 $1$ 的个数，令 $l(n)$ 代表 $n$ 末尾 $1$ 的个数。

显然 $T_i=l(n)+1,\Phi(n)=l(n)-1$，则 $A_i$ 可以取 $2$。

而 $\Phi(n)-\Phi(0) \sim \log n \le n$，则 $O(\sum T_i) = n$。

例题 4

KMP 算法。

令 $\Phi(n)$ 代表当前所代表的的节点在 $next$ 树中的深度。

则 $T_i-\Delta \Phi=1$，$O(\sum T_i)=n$。

均摊复杂度

我们可以这样计算快速排序的时间复杂度：

$T(1)=1\\ T(n)=T(c)+T(n-c)+n,c\in \text{rand}[1,n-1]$

假设 $T(n)=n^\alpha\log^\beta n$，则我们可以采用积分的方式，这里我们验证 $T(n)=n\log n$ 的正确性

$O(n\log n)=O(\frac{2\int n \log n \text{d} n+n^2}{n})=O(\frac{n^2\log n-\frac{n^2}{2}+n^2}{n})$

成立。