# 渐进表示法

1. $O$表示渐进上界，$f(n)=O(g(n))$，如果存在正常数$c$和$n_0$使得对于所有$n\geq n_0$都有$0\leq f(n)\leq cg(n)$。

$O(g(n))=\{f(n):存在常数c>0,n_0>0使得\forall n\geq n_0,0\leq f(n)\leq cg(n)\}$

2.  $\Omega$表示渐进下界

$\Omega(g(n))=\{f(n):存在常数c>0,n_0>0使得\forall n\geq n_0,0\leq cg(n)\leq f(n)\}$

3. $\Theta$表示渐进紧确界

$\Theta(g(n))=O(g(n))\cap \Omega(g(n))$

4. $o$表示严格上界，$f(n)=o(g(n))$，如果对于任意正常数$c$，都存在一个$n_0>0$使得对于所有$n\geq n_0$都有$0\leq f(n)<cg(n)$

5. $\omega$表示严格下界，$f(n)=\omega(g(n))$，如果对于任意正常数$c$，都存在一个$n_0>0$使得对于所有$n\geq n_0$都有$0\leq cg(n)<f(n)$

6. 传递性、自反性、对称性、反对称性

7. 不完备，如果某个函数是周期性波动的函数，则无法确定地找到一个函数来表示它的渐进上界或者渐进下界，如$f(n)=n,g(n)=n^{1-sin(n\pi/2)}$

8. $f^{(i)}(n)=\begin{cases}n,i=0\\f(f^{(i-1)}(n)),i>0\end{cases}$

9. $\lg^*n=\min\{i\geq0:\lg^{(i)}n\leq1\}$

# 递归表达式的时间复杂度

1. 代入法，猜到一个上界，数学归纳法

2. 递归树法，画出递归树，计算每一层的复杂度，求和

3. 主函数法，$T(n)=aT(n/b)+f(n)$，其中$a\geq1,b>1$，$f(n)$是一个渐进正函数

    1. $f(n)=O(n^{log_ba-\epsilon})$，则$T(n)=\Theta(n^{log_ba})$
    2. $f(n)=\Theta(n^{log_ba}\lg^kn)$，其中$k\geq0$，则$T(n)=\Theta(n^{log_ba}\lg^{k+1}n)$
    3. $f(n)=\Omega(n^{log_ba+\epsilon})$，且存在常数$c<1$和$n_0$使得对于所有$n\geq n_0$都有$af(n/b)\leq cf(n)$，则$T(n)=\Theta(f(n))$