大O符号

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

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

使用

无穷大渐近

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

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

这样，針對第一個例子${\displaystyle T(n)=4n^{2}-2n+2}$ ，大O符号就记下剩余的部分，写作：

${\displaystyle T(n)\in \mathrm {O} (n^{2})}$ 

或

${\displaystyle T(n)=\mathrm {O} (n^{2})}$ 

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

无穷小渐近

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

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

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

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

形式化定义

給定兩個定義在實數某子集上的關於${\displaystyle x}$ 的函數${\displaystyle f(x)}$ 和${\displaystyle g(x)}$ ，當${\displaystyle x}$ 趨近於無窮大時，存在正实數${\displaystyle M}$ ，使得對於所有充分大（英语：sufficiently large）的${\displaystyle x}$ ，都有${\displaystyle f(x)}$ 的絕對值小於等於${\displaystyle M}$ 乘以${\displaystyle g(x)}$ 的絕對值，那麼我們就可以說，當${\displaystyle x\to \infty }$ 時，

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

也就是說，假如存在正實數${\displaystyle M}$ 和實數${\displaystyle x}$ ₀，使得對於所有的${\displaystyle x\geq x_{0}}$ ，均有：${\displaystyle |f(x)|\leq \ M|g(x)|}$ 成立，我們就可以認爲，${\displaystyle f(x)=\mathrm {O} (g(x))}$ 。

在很多情況下，我們會省略“當${\displaystyle x}$ 趨近於無限大時”這個前提，而簡寫爲：

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

此概念也可以用於描述函數${\displaystyle f}$ 在接近實數${\displaystyle a}$ 時的行爲，通常${\displaystyle a=0}$ 。當我們說，當${\displaystyle x\to a}$ 時，有${\displaystyle f(x)=\mathrm {O} (g(x))}$ ，也就相當於稱，當且僅當存在正實數${\displaystyle M}$ 和實數${\displaystyle \delta }$ ，使得對於所有的${\displaystyle 0\leq |x-a|\leq \delta }$ ，均有${\displaystyle |f(x)|\leq \ M|g(x)|}$ 成立。

如果當${\displaystyle x}$ 和${\displaystyle a}$ 足夠接近時，${\displaystyle g(x)}$ 的值仍不爲0，這兩種定義就可以統一用上極限來表示：

當且僅當${\displaystyle \limsup _{x\to a}\left|{\frac {f(x)}{g(x)}}\right|<\infty }$ 時，有${\displaystyle f(x)=\mathrm {O} (g(x))}$ 。

例子

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

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

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

由${\displaystyle f(x)=\mathrm {O} (g(x))}$ ，可得：

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

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

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

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

${\displaystyle {\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}}}$ 

故${\displaystyle M}$ 可以为13。故两者都存在。

常用的函数阶

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

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

一些相关的渐近符号

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

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