大O符号

大O符号（Big O notation），又称为渐近符号，是用于描述函数渐近行为的数学符号。更确切地说，它是用另一个（通常更简单的）函数来描述一个函数数量级的渐近上界。在数学中，一般是用来刻画被截断的无穷级数尤其是渐近级数的剩余项；在计算机科学中，用来分析算法复杂性的方面非常有用。

大O符号是由德国数论学家保罗·巴赫曼在其1892年的著作《解析数论》（Analytische Zahlentheorie）首先引入的。而这个记号则是在另一位德国数论学家爱德蒙·兰道的著作中才推广的，因此会有时又称为兰道符号（Landau symbols）。代表“order of ...”（……阶）的大O，最初是一个大写希腊字母“Ο”（omicron），现今用的是大写拉丁字母“O”。

## 使用

### 无穷大渐近

大O符号在分析算法效率的时候非常有用。举个例子，解决一个规模为$n$的问题所花费的时间（或者所需步骤的数目）可以表示为：$T(n)=4n^2-2n+2$。当$n$增大时，$n^2$项将开始占主导地位，而其他各项可以被忽略。举例说明：当$n=500$，$4n^2$项是$2n$项的1000倍大，因此在大多数场合下，省略后者对表达式的值的影响将是可以忽略不计的。

进一步看，如果我们与任一其他级的表达式比较，$n^2$项的系数也是无关紧要的。例如：一个包含$n^3$或$n^2$项的表达式，即使$T(n)=1,000,000\cdot n^2$，假定$U(n)=n^3$，一旦$n$增长到大于1,000,000，后者就会一直超越前者（$T(1,000,000)=1,000,000^3=U(1,000,000)$）。

这样，针对第一个例子$T(n)=4n^2-2n+2$，大O符号就记下剩余的部分，写作：

$$T(n)\in\Omicron(n^2)$$

或

$$T(n)=\Omicron(n^2)$$

并且我们就说该算法具有$n^2$阶（平方阶）的时间复杂度。

### 无穷小渐近

大O也可以用来描述数学函数估计中的误差项。例如$e^x$的泰勒展开：

$e^x=1+x+\frac{x^2}{2}+\hbox{O}(x^3)\qquad$当$x \to 0$时

这表示，如果$x$足够接近于0，那么误差$e^x - \left(1 + x + \frac{x^2}{2}\right)$的绝对值小于$x^3$的某一常数倍。

注：泰勒展开的误差余项$r_3(x)$是关于$x^3$一个高阶无穷小量，用小o来表示，即：$r_3(x)$=$o(x^3)$，也就是$\lim_{x \to 0} \frac{r_3(x)}{x^3}=0.$

## 形式化定义

给定两个定义在实数某子集上的关于$x$的函数$f(x)$和$g(x)$，当$x$趋近于无穷大时，存在正实数$M$，使得对于所有充分大的$x$，都有$f(x)$的绝对值小于等于$M$乘以$g(x)$的绝对值，那么我们就可以说，当$x \to \infty$时。

$$f(x)=\Omicron(g(x))$$

也就是说，假如存在正实数$M$和实数$x$0，使得对于所有的$x \ge x_0$，均有：$|f(x)| \le \ M |g(x)|$成立，我们就可以认为，$f(x)=\Omicron(g(x))$。

在很多情况下，我们会省略“当$x$趋近于无限大时”这个前提，而简写为：

$$f(x)=\Omicron(g(x))$$

此概念也可以用于描述函数$f$在接近实数$a$时的行为，通常$a = 0$。当我们说，当$x \to a$时，有$f(x)=\Omicron(g(x))$，也就相当于称，当且仅当存在正实数$M$和实数$\delta$，使得对于所有的$0 \le |x - a| \le \delta$，均有$|f(x)| \le \ M |g(x)|$成立。

如果当$x$和$a$足够接近时，$g(x)$的值仍不为0，这两种定义就可以统一用上极限来表示：

当且仅当$\limsup_{x\to a} \left|\frac{f(x)}{g(x)}\right| < \infty$时，有$f(x)=\Omicron(g(x))$。

## 例子

在具体的运用中，我们不一定使用大O符号的标准定义，而是使用几条简化规则来求出关于函数$f$的大O表示：

- 假如$f(x)$是几项之和，那么只保留增长最快（通常是阶最高）的项，其他项省略。
- 假如$f(x)$是几项之积，那么常数（不取决于x的乘数）省略。

比如，使$f(x) = 6x^4 - 2x^3 + 5$，我们想要用大O符号来简化这个函数，来描述$x$接近无穷大时函数的增长情况。此函数由三项相加而成，$6x^4$，$-2x^3$和$5$。由于增长最快的是$6x^4$这一项（因为阶最高，在x接近无穷大时，其对和的影响会大大超过其余两项），应用第一条规则，保留它而省略其他两项。对于$6x^4$，由两项相乘而得，$6$和$x^4$；应用第二条规则，$6$是无关x的常数，所以省略。最后结果为$x^4$，也即$g(x) = x^4$。故有：

由$f(x) = \Omicron(g(x))$，可得：

$$6x^4 - 2x^3 + 5 = O(x^4)$$

我们可以将上式扩展为标准定义形式：

对任意$x \ge x_0$，均有$|f(x)| \le M|g(x)|$，也就是$6x^4 - 2x^3 + 5 \le M|x^4|$

可以（粗略）求出$M$和$x_0$的值来验证。使$x_0=1$：

$$\begin{align}|6x^4 - 2x^3 + 5| &\le 6x^4 + |2x^3| + 5\\ <pre> &\le 6x^4 + 2x^4 + 5x^4\\ &\le 13x^4\end{align}$$

故$M$可以为13。故两者都存在。

## 常用的函数阶

下面是在分析算法的时候常见的函数分类列表。所有这些函数都处于$n$趋近于无穷大的情况下，增长得慢的函数列在上面。$c$是一个任意常数。

符号｜名称

$\Omicron(1)\!$｜常数（阶，下同）

$\Omicron(\log n)\!$｜对数

$\Omicron[(\log n)^c]\!$｜多对数

$\Omicron(n)\!$｜线性，次线性

$\Omicron(n\log^*n)\!$｜$\log^*n$为迭代对数

$\Omicron(n \log n)\!$｜线性对数，或对数线性、拟线性、超线性

$\Omicron( n^2)\!$｜平方

$\Omicron(n^c), \operatorname{Integer}(c>1)$｜多项式，有时叫作“代数”（阶）

$\Omicron(c^n)\!$｜指数，有时叫作“几何”（阶）

$\Omicron(n!)\!$｜阶乘，有时叫做“组合”（阶）

## 一些相关的渐近符号

大O是最经常使用的比较函数的渐近符号。

符号｜定义

$f(n)=\Omicron (g(n))$｜渐近上限

$f(n)=o(g(n))$｜Asymptotically negligible渐近可忽略不计（$\lim{} \frac{f(n)}{g(n)} = 0$）

$f(n)=\Omega(g(n))$｜渐近下限（当且仅当$g(n) = \Omicron(f(n))$）

$f(n) = \omega (g(n))$｜Asymptotically dominant渐近主导（当且仅当$g(n)=o(f(n))$）

$f(n) = \Theta(g(n))$｜Asymptotically tight bound渐近紧约束（当且仅当$f(n) = \Omicron(g(n))$且$f(n)=\Omega(g(n))$）

## 注意

大O符号经常被误用：有的作者可能会使用大O符号表达大Θ符号的含义。因此在看到大O符号时应首先确定其是否为误用。