定义
$\Theta(f(n))$
同阶函数集合
$\Theta(g(n))=\begin{Bmatrix} f(n) | \exists c1, c2>0, n0,\forall n>n0, c1g(n)\leq f(n)\leq c2g(n)\end{Bmatrix} $
$f(n)\in \Theta(g(n))$,则称$f(n)$和$g(n)$为同阶函数,$f(n)$的渐进紧界是$g(n)$。
$O(f(n))$
低阶函数集合
$O(g(n))=\begin{Bmatrix} f(n) | \exists c>0, n0,\forall n>n0, 0\leq f(n)\leq cg(n)\end{Bmatrix} $
$f(n)\in O(g(n))$,则称$f(n)$是$g(n)$的低阶函数,$f(n)$的渐进上界是$g(n)$。
注意：$\Theta(g(n))\subseteq O(g(n))$
$\Omega(f(n))$
高阶函数集合
$\Omega(g(n))=\begin{Bmatrix} f(n) | \exists c>0, n0,\forall n>n0, 0\leq cf(n)\leq g(n)\end{Bmatrix} $
$f(n)\in \Omega(g(n))$,则称$f(n)$是$g(n)$的高阶函数,$f(n)$的渐进上界是$g(n)$。
$o(f(n))$
严格低阶函数
$O(g(n))=\begin{Bmatrix} f(n) | \exists c>0, n0,\forall n>n0, 0\leq f(n)< cg(n)\end{Bmatrix} $
$f(n)\in o(g(n))$,则称$f(n)$是$g(n)$的高阶函数,$f(n)$的严格上界是$g(n)$。
$\omega(f(n))$
严格高阶函数
$\omega(g(n))=\begin{Bmatrix} f(n) | \exists c>0, n0,\forall n>n0, 0\leq cf(n)\leq g(n)\end{Bmatrix} $
$f(n)\in \Omega(g(n))$,则称$f(n)$是$g(n)$的高阶函数,$f(n)$的严格下界是$g(n)$。
$f(n)=o(g(n))
\Leftrightarrow\lim\limits_{n\to\infty}\frac{f(n)}{g(n)}=0$