大O符号

注：“order”在全文中被译为“阶”，也可以另译为“数量级”。

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

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

使用[编辑]

这个符号有两种形式上很接近但迥然不同的使用方法：无穷大渐近与无穷小渐近。然而这个区别只是在运用中的而不是原则上的——除了对函数自变量的一些不同的限定， “大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)$ ）。

这样，大O符号就记下剩余的部分，写作：

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

或

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

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

无穷小渐近[编辑]

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

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

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

形式化定义[编辑]

給定兩正值函數 $f$ 和 $g$ , 定義:

$f(n)=\Omicron(g(n))$ , 條件為: 存在正數 $c$ 和 $N$ , 使得對於所有的 $n \geq N$ , 有 $f(n) \leq cg(n)$

上述的定義表明，當 $n$ 足夠大，大過一個特定的 $N$ 時，且存在一個正數 $c$ , 使得 $f$ 不大於 $cg$ , 則 $f$ 是 $g$ 的 $\Omicron$ 表示。 $f$ 和 $g$ 的關係可以理解為 $g(n)$ 是 $f(n)$ 的一個上界，也可以理解為 $f$ 最終至多增漲的速度與 $g$ 一樣快，但不會超過 $g$ 的增漲速度。

常用的函数阶[编辑]

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

符号	名称
$\Omicron(1)\!$	常数（阶，下同）
$\Omicron(\log^*n)\!$	迭代对数
$\Omicron(\log n)\!$	对数
$\Omicron[(\log n)^c]\!$	多对数
$\Omicron(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))$ )