本文最后更新于:1 年前
渐进记号
一、五种渐进记号
- 大$O$记号:
对于给定函数$g(n)$,$f(n)=O(g(n))$:存在正常量$c$和$n_{0}$,使得对所有$n \geq n_{0}$,有$0 \leq f(n) \leq cg(n)$成立。$f(n)$只有一个渐进上界,$f(n)$的阶不高于$g(n)$的阶。
- $\Omega$记号:
对于给定函数$g(n)$,$f(n)=O(g(n))$:存在正常量$c$和$n_{0}$,使得对所有$n \geq n_{0}$,有$0 \leq cg(n) \leq f(n)$成立。$f(n)$只有一个渐进下界,$f(n)$的阶不低于$g(n)$的阶。
- $\Theta$记号:
对于给定函数$g(n)$,$f(n)=\Theta(g(n))$:存在正常量$c_{1}$,$c_{2}$和$n_{0}$,使得对所有$n \geq n_{0}$,有$0 \leq c_{1}g(n) \leq f(n) \leq c_{2}g(n)$成立。$\Theta$记号渐进地给出了一个函数的上界和下界,$f(n)$的阶等于$g(n)$的阶
若$f(n)=O(g(n))$且$f(n)= \Omega (g(n))$,则$f(n)= \Theta (g(n))$。
- 小$o$记号:
对于给定函数$g(n)$,$f(n)=O(g(n))$:存在正常量$c > 0$和$n_{0} > 0$,使得对所有$n \geq n_{0}$,有$0 \leq f(n) < cg(n)$成立。$f(n)$只有一个渐进紧确上界,$f(n)$的阶低于$g(n)$的阶。
- $\omega$记号:
对于给定函数$g(n)$,$f(n)=O(g(n))$:存在正常量$c > 0$和$n_{0} > 0$,使得对所有$n \geq n_{0}$,有$0 \leq cg(n) < f(n)$成立。$f(n)$只有一个渐进紧确下界,$f(n)$的阶高于$g(n)$的阶。
二、 相关定理
- 定理1:
(1)如果$\lim_{n \to +\infty} \frac{f(n)}{g(n)}$存在,且为某个常数$c$,则$f(n)= \Theta (g(n))$
(2)如果$\lim_{n \to +\infty} \frac{f(n)}{g(n)}=0$,则$f(n)= O (g(n))$
(3)如果$\lim_{n \to +\infty} \frac{f(n)}{g(n)}=\infty$,则$f(n)= \omega (g(n))$
由定理1可以导出两个重要结果:
(1)多项式函数的阶低于指数函数的阶:
(2)对数函数的阶低于幂函数的阶:
- 定理2,传递性:
若$f(n)= \Theta (g(n))$,且$g(n)=\Theta (h(n))$,则$f(n)=\Theta(h(n))$。对于大$O$、小$o$、$\Omega$、$\omega$同样成立。
- 定理3:
该性质可推广到有限个函数。算法由有限个步骤构成,若每一步的时间复杂度函数的上界都是$h(n)$,那么算法的时间复杂度函数可以写作$O(h(n))$
三、相关性质
- 1、自反性:
- 2、对称性:
$f(n)=\Theta(g(n))$,当且仅当$g(n)=\Theta(f(n))$
- 3、转置对称性:
$f(n)=O(g(n))$当且仅当$g(n)=\Omega(f(n))$
$f(n)=o(g(n))$当且仅当$g(n)=\omega(f(n))$
四、几类重要函数
至少指数函数级: $2^{n}$, $3^{n}$, $n!$, $2^{2^{n}}$, $n2^{n}$, $(\log n)^{\log n}=n^{\log \log n}$
多项式级: $n$, $n^{2}$, $n {\rm log}n$, $n^{\frac{1}{2}}$, $n^{3}$, ${\rm log}(n!)=\Theta(n {\rm log}n)$
对数多项式级: ${\rm log}n$, ${\rm log}^{2}n$, ${\rm log log}n$, $\sqrt{\log n}$
取整函数
$\lfloor x \rfloor$:向下取整,$\lceil x \rceil$:向上取整
一些性质:
参考资料
《算法导论》
本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!