算法复杂度分析的标记符号

介绍下在分析算法复杂度时用到的标记符号，及其数学来源。

这些标记符号开始源于德国数学家 Paul Bachmann 和 Edmund Landau 的发明，后经 Knuth 的整理，形成了现在熟悉的这些渐进符号（asymptotic notation）。

$O$ 记号

开始叫做 big-O¹，后经过 Knuth 整理，也可以表示为 big Omicron 。

形式化描述

$f(x) = O(g(x)),\quad x\to \infty $

等价于：

$\exists (M\gt0, x_0)$ ，使得所有 $x \geqslant x_0$ ，都有 $\vert f(x)\vert \leqslant M g(x)$ ， 其中函数 $g(x)$ 对于足够大的 $x$ 来说总是正数。

$o$ 记号

叫做 little-o ，也可以叫做 little omicron 。相比于 big-O ，little-o 的限制更加严格。

形式化描述

$f(x) = o(g(x)),\quad x\to \infty $

等价于：

$\forall \epsilon \gt 0,\ \exists x_0$ ，使得所有 $x \geqslant x_0$ ，都有 $\vert f(x)\vert \leqslant \epsilon g(x)$ ， 其中函数 $g(x)$ 对于足够大的 $x$ 来说总是正数。²

这个定义形式上就类似微分里面的上极限的定义。

另一种形式

按照定义高阶无穷小的方式，它还可以写作：

$\displaystyle \lim_{x\to\infty}{\frac{f(x)}{g(x)}} = 0$

也就是说，$g(x)$ 是更高阶的一个函数，是 $f(x)$ 的严格上限。这种 little-o 的记号在泰勒展开式里作为余项也用到过。

与 $O$ 的关系

记号描述得其实是一种集合成员与集合的概念，这样我们就清楚了 big-O 实际上就是同阶函数和更高阶函数 $o$ 两个不相交集合的并集 ³。

$\Omega$ & $\omega$ 记号

分别叫做 big Omega 和 little omega ，根据 Knuth 的归纳调整，big Omega 成为了：

$f(x) = \Omega(g(x)) \Leftrightarrow g(x) = O(f(x))$

而 little omega 则对应了：

$f(x) = \omega(g(x)) \Leftrightarrow g(x) = o(f(x))$

但是按照函数阶的集合的观点更直观，big Omega 代表小于或等于这个阶的函数集合，而 little omega 则代表了；严格小于这个阶的函数集合。

$\Theta$ 记号

叫做 big Theta。根据 Knuth 的定义：

$f(x) = \Theta(g(x)) \Leftrightarrow f(x) = O(g(x)) = \Omega(g(x))$

是说给出的 $g(x)$ 同时满足了 big-O 和 big Omega 这两个集合的定义。

总结

可以按照如下表对复杂度记号进行理解：

记号	逻辑关系
$O$	$\leqslant$
$o$	$\lt$
$\Theta$	$\simeq$
$\Omega$	$\geqslant$
$\omega$	$\gt$

备查时间复杂度表

注解