函数的增长

函数的增长

1.$\Theta$记号

$\Theta(g(n))=\{f(n):存在正常量c_1、c_2和n_0,使得对所有n\ge n_0,有0\le c_1g(n)\le f(n) \le c_2g(n)\}$

理解为当$n$足够大时，$f(n)$能完全夹入$g(n)$的两个常数倍的函数值之间，因此$g(n)$时$f(n)$的一个渐进紧确界。$\Theta(g(n))$表达的是一组函数的集合，$f(n)$是能归到集合里的某个具体函数。举个例子: $f(n)=\frac{1}{2}n^2-3n$，寻找满足条件的$c_1,c_2$，使对足够大的$n$，$c_1n^2\le\frac{1}{2}n^2-3n\le c_2n^2$恒成立，即$c_1 \le \frac{1}{2}-\frac{3}{n}\le c_2$，取$c_1\le1/14$，$c_2\ge1/2$即可。因此$\frac{1}{2}n^2-3n=\Theta(n^2)$。这个例子也告诉我们，函数的低阶项在确定渐进紧确界时可忽略。

2.$O$记号

$O(g(n))=\{f(n):存在正常量c和n_0,使得对所有n\ge n_0,有0\le f(n)\le cg(n)\}$

因此$g(n)$某个常量倍数是$f(n)$的渐进上界，而不要求是紧确的上界。例如$n=O(n^2)$。可能紧确也可能不紧确。

3.$\Omega$记号

$\Omega(g(n))=\{f(n):存在正常量c和n_0,使得对所有的n\ge n_0,有0\le cg(n)\le f(n)\}$

这个记号给出了$f(n)$的渐进下界。

若$f(n)$的渐进上界和渐进下界相等，则它也是$f(n)$的渐进确界

4.$o$记号

$o(g(n))=\{f(n):对任意正常量c>0,存在常量n_0>0,使得对所有n\ge n_0,有0 \le f(n) < cg(n)\}$

由于$c$的任意性，$o$记号给出的是非渐进紧确的上界，而且一定不可能是紧确的。

5.$\omega$记号

$\omega(g(n))=\{f(n):对任意正常量c>0,存在常量n_0>0,使得对所有n\ge n_0,有0 \le cg(n) < f(n)\}$

$\omega$记号会给出非渐进紧确的下界。

6.性质

传递性 若$f(n)=K(g(n)),g(n)=K(h(n))$，则$f(n)=K(h(n)),K=\Theta,O,\Omega,o,\omega$

自反性 $f(n)=K(f(n)),K=\Theta,O,\Omega$

对称性 $f(n)=\Theta(g(n))\leftrightarrow g(n)=\Theta(f(n))$

转置对称性

$f(n)=O(g(n))\leftrightarrow g(n)=\Omega(f(n))$

$f(n)=o(g(n))\leftrightarrow g(n)=\omega(f(n))$