大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 \mathrm {O} (n^{2})$

或

$T(n)=\mathrm {O} (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)=\mathrm {O} (g(x))$

也就是说，假如存在正实数$M$和实数$x$₀，使得对于所有的$x\geq x_{0}$，均有：$|f(x)|\leq \ M|g(x)|$成立，我们就可以认为，$f(x)=\mathrm {O} (g(x))$。

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

$f(x)=\mathrm {O} (g(x))$

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

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

当且仅当$\limsup _{x\to a}\left|{\frac {f(x)}{g(x)}}\right|<\infty$时，有$f(x)=\mathrm {O} (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)=\mathrm {O} (g(x))$，可得：

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

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

对任意$x\geq x_{0}$，均有$|f(x)|\leq M|g(x)|$，也就是$6x^{4}-2x^{3}+5\leq M|x^{4}|$

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

${\begin{aligned}|6x^{4}-2x^{3}+5|&\leq 6x^{4}+|2x^{3}|+5\\&\leq 6x^{4}+2x^{4}+5x^{4}\\&\leq 13x^{4}\end{aligned}}$

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

常用的函数阶

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

符号	名称
$\mathrm {O} (1)\!$	常数（阶，下同）
$\mathrm {O} (\log n)\!$	对数
$\mathrm {O} [(\log n)^{c}]\!$	多对数
$\mathrm {O} (n)\!$	线性，次线性
$\mathrm {O} (n\log ^{*}n)\!$	$\log ^{*}n$为迭代对数
$\mathrm {O} (n\log n)\!$	线性对数，或对数线性、拟线性、超线性
$\mathrm {O} (n^{2})\!$	平方
$\mathrm {O} (n^{c}),\operatorname {Integer} (c>1)$	多项式，有时叫作“代数”（阶）
$\mathrm {O} (c^{n})\!$	指数，有时叫作“几何”（阶）
$\mathrm {O} (n!)\!$	阶乘，有时叫做“组合”（阶）

一些相关的渐近符号

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

符号	定义
$f(n)=\mathrm {O} (g(n))$	渐近上限
$f(n)=o(g(n))$	Asymptotically negligible渐近可忽略不计（$\lim {}{\frac {f(n)}{g(n)}}=0$）
$f(n)=\Omega (g(n))$	渐近下限（当且仅当$g(n)=\mathrm {O} (f(n))$）
$f(n)=\omega (g(n))$	Asymptotically dominant渐近主导（当且仅当$g(n)=o(f(n))$）
$f(n)=\Theta (g(n))$	Asymptotically tight bound渐近紧约束（当且仅当$f(n)=\mathrm {O} (g(n))$且$f(n)=\Omega (g(n))$）

注意

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

参看

• O（拉丁字母）
• 小o符号
• 大Ω符号
• 大Θ符号

参考文献

来源

书籍

• 严蔚敏、吴伟民：《数据结构：C语言版》. 清华大学出版社，1996. ISBN 7-302-02368-9. 1.4节 算法和算法分析，pp. 14-17.
• 朱青：《计算机算法与程序设计》. 清华大学出版社，2009.10。ISBN 978-7-302-20267-7. 1.4节 算法的复杂性分析，pp. 16-17.

延伸阅读

• Hardy, G. H. Orders of Infinity: The 'Infinitärcalcül' of Paul du Bois-Reymond. Cambridge University Press. 1910. 
• Knuth, Donald. 1.2.11: Asymptotic Representations. Fundamental Algorithms. The Art of Computer Programming 1 3rd. Addison–Wesley. 1997. ISBN 0-201-89683-4. 
• Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford. 3.1: Asymptotic notation. Introduction to Algorithms 2nd. MIT Press and McGraw–Hill. 2001. ISBN 0-262-03293-7. 
• Sipser, Michael. Introduction to the Theory of Computation. PWS Publishing. 1997: 226–228. ISBN 0-534-94728-X. 
• Avigad, Jeremy; Donnelly, Kevin. Formalizing O notation in Isabelle/HOL (PDF). International Joint Conference on Automated Reasoning. 2004. doi:10.1007/978-3-540-25984-8_27. 
• Black, Paul E. Black, Paul E. , 编. big-O notation. Dictionary of Algorithms and Data Structures. U.S. National Institute of Standards and Technology. 11 March 2005 [December 16, 2006]. （原始内容存档于2019-05-20）. 
• Black, Paul E. Black, Paul E. , 编. little-o notation. Dictionary of Algorithms and Data Structures. U.S. National Institute of Standards and Technology. 17 December 2004 [December 16, 2006]. （原始内容存档于2020-11-01）. 
• Black, Paul E. Black, Paul E. , 编. Ω. Dictionary of Algorithms and Data Structures. U.S. National Institute of Standards and Technology. 17 December 2004 [December 16, 2006]. （原始内容存档于2021-01-25）. 
• Black, Paul E. Black, Paul E. , 编. ω. Dictionary of Algorithms and Data Structures. U.S. National Institute of Standards and Technology. 17 December 2004 [December 16, 2006]. （原始内容存档于2021-01-26）. 
• Black, Paul E. Black, Paul E. , 编. Θ. Dictionary of Algorithms and Data Structures. U.S. National Institute of Standards and Technology. 17 December 2004 [December 16, 2006]. （原始内容存档于2021-01-26）.