大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符號
• 大Ω符号
• 大Θ符号

参考文献

引用

来源

延伸閱讀