本文最后更新于：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$：向上取整

  • 一些性质：

参考资料