大O符号

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

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

这个符号有两种形式上很接近但迥然不同的使用方法：无穷大渐进与无穷小渐进。然而这个区别-{只是}-在运用中的而不是原则上的——除了对函数自变量的一些不同的限定，“大O”的形式定义在两种情况下都是相同的。

无穷大渐进

在分析算法效率的时候非常有用。举个例子，解决一个规模为 n 的问题所花费的时间（或者所需步骤的数目）可以被求得：T(n) = 4n² − 2n + 2。

当n增大时，n²项将开始占主导地位，而其他各项可以被忽略——举例说明：当n = 500，4n²项是2n项的1000倍大，因此在大多数场合下，省略后者对表达式的值的影响将是可以忽略不计的。

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

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

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

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

无穷小渐进

大O也可以用来描述数学函数估计中的误差项。例如：

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

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

形式化定义

$f(x)=O(g(x)) \Leftrightarrow \exists C,x_{0} : \left( x \ge x_{0} \Rightarrow f(x) \le C g(x) \right)$

常用的函数阶

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

符号	名称
O(1)	常数（阶，下同）
O(log * n)	迭代对数
O(logn)	对数
O([logn]c)	多对数
o(n)	次线性
O(n)	线性
O(nlogn)	线性对数，或对数线性、拟线性、超线性
O(n2)	平方
O(nc), c > 1	多项式，有时叫作“代数”（阶）
O(cn)	指数，有时叫作“几何”（阶）
O(n!)	阶乘，有时叫做“组合”（阶）

一些相关的渐进符号

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

符号	定义
f(n) = O(g(n))	渐进上限
f(n) = o(g(n))	asymptotically negligible (M = 0)
f(n) = Ω(g(n))	渐进下限 (当且仅当 g(n) = O(f(n)))
f(n) = ω(g(n))	asymptotically dominant (当且仅当 g(n) = o(f(n)))
f(n) = Θ(g(n))	紧确的上下界 (当且仅当 both f(n) = O(g(n)) and g(n) = O(f(n)))

参看

• 大Ω符号
• 大Θ符号

参考资料

• 严蔚敏，吴伟民。数据结构：C语言版。北京清华大学出版社，1996。ISBN 7-302-02368-9。1.4节 算法和算法分析，14-17页。
• 部分来自维基百科中的大O符号，使用GFDL版权发布。