大O符号
$f(n)=O(g(n))$ 的意思是存在常数 $c>0$ 和 $n>{n}_{o}$ ，使得
$$0 \leq f(n) \leq cg(n)$$
其中 $n\geq{n}_{o}$
例子
$2{n}^{2}=O({n}^{3})$
其实在这些符号的等号不是相等的意思，而是是的意思。在这个例子中，$O({n}^{3})$ 是$2{n}^{2}$的上界，这是显而易见的。
$\Omega$符号
有上界就会有下界，定义与O差不多，只是符号反了过来
例子
$$\sqrt{n}=\Omega(lgn)$$
$\Theta$符号
定义为$O$与$\Omega$的交集。
$$ \Theta(g(n))=O(g(n))\bigcap\Omega(g(n)) $$
解递归
解递归没有特定的方法，这里有三种解递归的方法。
方法一：递推法
递推法常用来检验解递归公式的正确性，因为其第一步的动作是要猜测递归的解大概是什么。下面是基本流程
- 猜测结果是什么
- 用归纳法验证
- 求出常数项
例子
$$T(n)=4T(n/2)+n$$
我们知道 $T(1)=\Theta(1)$。
先猜测$T(n)=O({n}^{3})$
归纳法验证
假设对于所有$k<n$，$T(k) \leq c{k}^{3}$，那么
$$ T(n)=4T(n/2)+n=4c {(\frac{kn}{2})}^{3} +n= \frac{1}{2} c{n}^{3}+n $$
$$
= c{n}^{3}- \frac{1}{2}c({n}^{3}-n) \leq c{n}^{3}如果 \frac{1}{2}c{n}^{3}-n \geq 0
$$
$$ e.g c \geq 1 n \geq 1 $$
方法二：递归书
递归书很好用，但是不严谨，有猜测的成分。基本思想就是画递归树，然后把每次递归的时间加起来，就是总时间了。
例子
$$T(n) = T(\frac{n}{4}) + T(\frac{n}{2}) + {n}^{2}$$
方法三：主定理
使用主定理的局限较大，但是很方便。它只能在以下形式的递归公式上用。
$$ T(n) = aT(\frac{n}{b}) + f(n) $$
注意$a \geq 0$ ,$b>1$ $f(n)$渐近趋正
使用主定理就是要比较$f(n)$和${n}$^${\log_{b}}^{a}$的关系，有三种情况
情况一
$f(n) <{n}$^${\log_{b}}^{a}$，这个时候
$T(n)=\Theta ({n}$^${\log_{b}}^{a})$
情况二
$f(n) ={n}$^${\log_{b}}^{a}$，这个时候
$T(n)=\Theta ({n}$^${\log_{b}}^{a} {\lg}^{k+1}n )$
$$k \geq 0$$
情况三
$f(n) >{n}$^${\log_{b}}^{a}$，这个时候
$$T(n)=\Theta (f(n))$$