大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)) $$

解递归

解递归没有特定的方法,这里有三种解递归的方法。

方法一:递推法

递推法常用来检验解递归公式的正确性,因为其第一步的动作是要猜测递归的解大概是什么。下面是基本流程

  1. 猜测结果是什么
  2. 用归纳法验证
  3. 求出常数项

例子

$$T(n)=4T(n/2)+n$$

我们知道 $T(1)=\Theta(1)$。

  1. 先猜测$T(n)=O({n}^{3})$

  2. 归纳法验证

假设对于所有$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}$$

recursion_tree

方法三:主定理

使用主定理的局限较大,但是很方便。它只能在以下形式的递归公式上用。

$$ 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))$$