算法时间复杂度分析

定义

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