大O符号 （英语：Big O notation ），又称为渐进符号 ，是用于描述函数 渐近行为 的数学 符号。更确切地说，它是用另一个（通常更简单的）函数来描述一个函数数量级 的渐近上界 。在数学 中，它一般用来刻画被截断的无穷级数 尤其是渐近级数 的剩余项；在计算机科学 中，它在分析 算法 复杂性 的方面非常有用。
大O符号是由德国 数论 学家保罗·巴赫曼 在其1892年的著作《解析数论》（Analytische Zahlentheorie ）首先引入的。而这个记号则是在另一位德国数论学家艾德蒙·朗道 的著作中才推广的，因此它有时又称为朗道符号 （Landau symbols）。代表“order of ...”（……阶）的大O ，最初是一个大写希腊字母 “Ο ”（omicron），现今用的是大写拉丁字母 “O ”。
使用 无穷大渐近 大O符号在分析算法效率的时候非常有用。举个例子，解决一个规模为
n
{\displaystyle n}
T
(
n
)
=
4
n
2
−
2
n
+
2
{\displaystyle T(n)=4n^2-2n+2}
n
{\displaystyle n}
n
2
{\displaystyle n^2}
n
=
500
{\displaystyle n=500}
4
n
2
{\displaystyle 4n^2}
2
n
{\displaystyle 2n}
进一步看，如果我们与任一其他级的表达式比较，
n
2
{\displaystyle n^2}
系数 也是无关紧要的。例如：一个包含
n
3
{\displaystyle n^3}
n
2
{\displaystyle n^2}
T
(
n
)
=
1
,
000
,
000
⋅
n
2
{\displaystyle T(n)=1,000,000\cdot n^2}
U
(
n
)
=
n
3
{\displaystyle U(n)=n^3}
n
{\displaystyle n}
T
(
1
,
000
,
000
)
=
1
,
000
,
000
3
=
U
(
1
,
000
,
000
)
{\displaystyle T(1,000,000)=1,000,000^3=U(1,000,000)}
T
(
n
)
=
4
n
2
−
2
n
+
2
{\displaystyle T(n)=4n^2-2n+2}
T
(
n
)
∈
O
(
n
2
)
{\displaystyle T(n)\in\Omicron(n^2)}
或
T
(
n
)
=
O
(
n
2
)
{\displaystyle T(n)=\Omicron(n^2)}
并且我们就说该算法具有
n
2
{\displaystyle n^2}
时间复杂度 。
无穷小渐近 大O也可以用来描述数学函数估计中的误差项。例如
e
x
{\displaystyle e^x}
泰勒展开 ：
e
x
=
1
+
x
+
x
2
2
+
O
(
x
3
)
{\displaystyle e^x=1+x+\frac{x^2}{2}+\hbox{O}(x^3)\qquad}
x
→
0
{\displaystyle x \to 0}
这表示，如果
x
{\displaystyle x}
e
x
−
(
1
+
x
+
x
2
2
)
{\displaystyle e^x - \left(1 + x + \frac{x^2}{2}\right)}
绝对值 小于
x
3
{\displaystyle x^3}
注：泰勒展开的误差余项
r
3
(
x
)
{\displaystyle r_3(x)}
x
3
{\displaystyle x^3}
r
3
(
x
)
{\displaystyle r_3(x)}
o
(
x
3
)
{\displaystyle o(x^3)}
lim
x
→
0
r
3
(
x
)
x
3
=
0
{\displaystyle \textstyle \lim_{x \to 0} \displaystyle \frac{r_3(x)}{x^3}=0}
形式化定义 给定两个定义在实数 某子集上的关于
x
{\displaystyle x}
f
(
x
)
{\displaystyle f(x)}
g
(
x
)
{\displaystyle g(x)}
x
{\displaystyle x}
M
{\displaystyle M}
充分大 的
x
{\displaystyle x}
f
(
x
)
{\displaystyle f(x)}
M
{\displaystyle M}
g
(
x
)
{\displaystyle g(x)}
x
→
∞
{\displaystyle x \to \infty}
f
(
x
)
=
O
(
g
(
x
)
)
{\displaystyle f(x)=\Omicron(g(x))}
也就是说，假如存在正实数
M
{\displaystyle M}
x
{\displaystyle x}
0 ，使得对于所有的
x
≥
x
0
{\displaystyle x \ge x_0}
|
f
(
x
)
|
≤
M
|
g
(
x
)
|
{\displaystyle |f(x)| \le \ M |g(x)|}
f
(
x
)
=
O
(
g
(
x
)
)
{\displaystyle f(x)=\Omicron(g(x))}
在很多情况下，我们会省略“当
x
{\displaystyle x}
f
(
x
)
=
O
(
g
(
x
)
)
{\displaystyle f(x)=\Omicron(g(x))}
此概念也可以用于描述函数
f
{\displaystyle f}
a
{\displaystyle a}
a
=
0
{\displaystyle a = 0}
x
→
a
{\displaystyle x \to a}
f
(
x
)
=
O
(
g
(
x
)
)
{\displaystyle f(x)=\Omicron(g(x))}
当且仅当 存在正实数
M
{\displaystyle M}
δ
{\displaystyle \delta}
0
≤
|
x
−
a
|
≤
δ
{\displaystyle 0 \le |x - a| \le \delta}
|
f
(
x
)
|
≤
M
|
g
(
x
)
|
{\displaystyle |f(x)| \le \ M |g(x)|}
如果当
x
{\displaystyle x}
a
{\displaystyle a}
g
(
x
)
{\displaystyle g(x)}
上极限 来表示：
当且仅当
lim sup
x
→
a
|
f
(
x
)
g
(
x
)
|
<
∞
{\displaystyle \limsup_{x\to a} \left|\frac{f(x)}{g(x)}\right| < \infty}
f
(
x
)
=
O
(
g
(
x
)
)
{\displaystyle f(x)=\Omicron(g(x))}
例子 在具体的运用中，我们不一定使用大O符号的标准定义，而是使用几条简化规则来求出关于函数
f
{\displaystyle f}
假如
f
(
x
)
{\displaystyle f(x)}
假如
f
(
x
)
{\displaystyle f(x)}
比如，使
f
(
x
)
=
6
x
4
−
2
x
3
+
5
{\displaystyle f(x) = 6x^4 - 2x^3 + 5}
x
{\displaystyle x}
6
x
4
{\displaystyle 6x^4}
−
2
x
3
{\displaystyle -2x^3}
5
{\displaystyle 5}
6
x
4
{\displaystyle 6x^4}
6
x
4
{\displaystyle 6x^4}
6
{\displaystyle 6}
x
4
{\displaystyle x^4}
6
{\displaystyle 6}
x
4
{\displaystyle x^4}
g
(
x
)
=
x
4
{\displaystyle g(x) = x^4}
由
f
(
x
)
=
O
(
g
(
x
)
)
{\displaystyle f(x) = \Omicron(g(x))}
6
x
4
−
2
x
3
+
5
=
O
(
x
4
)
{\displaystyle 6x^4 - 2x^3 + 5 = O(x^4)}
我们可以将上式扩展为标准定义形式：
对任意
x
≥
x
0
{\displaystyle x \ge x_0}
|
f
(
x
)
|
≤
M
|
g
(
x
)
|
{\displaystyle |f(x)| \le M|g(x)|}
6
x
4
−
2
x
3
+
5
≤
M
|
x
4
|
{\displaystyle 6x^4 - 2x^3 + 5 \le M|x^4|}
可以（粗略）求出
M
{\displaystyle M}
x
0
{\displaystyle x_0}
x
0
=
1
{\displaystyle x_0=1}
|
6
x
4
−
2
x
3
+
5
|
≤
6
x
4
+
|
2
x
3
|
+
5
≤
6
x
4
+
2
x
4
+
5
x
4
≤
13
x
4
{\displaystyle \begin{align}|6x^4 - 2x^3 + 5| &\le 6x^4 + |2x^3| + 5\\
&\le 6x^4 + 2x^4 + 5x^4\\
&\le 13x^4\end{align}}
故
M
{\displaystyle M}
常用的函数阶 下面是在分析算法 的时候常见的函数分类列表。所有这些函数都处于
n
{\displaystyle n}
c
{\displaystyle c}
符号
名称
O
(
1
)
{\displaystyle \Omicron(1)\!}
常数 （阶，下同）
O
(
log
n
)
{\displaystyle \Omicron(\log n)\!}
对数
O
[
(
log
n
)
c
]
{\displaystyle \Omicron[(\log n)^c]\!}
多对数
O
(
n
)
{\displaystyle \Omicron(n)\!}
线性 ，次线性
O
(
n
log
∗
n
)
{\displaystyle \Omicron(n\log^*n)\!}
log
∗
n
{\displaystyle \log^*n}
迭代对数
O
(
n
log
n
)
{\displaystyle \Omicron(n \log n)\!}
线性对数 ，或对数线性、拟线性、超线性
O
(
n
2
)
{\displaystyle \Omicron( n^2)\!}
平方
O
(
n
c
)
,
Integer
(
c
>
1
)
{\displaystyle \Omicron(n^c), \operatorname{Integer}(c>1)}
多项式 ，有时叫作“代数”（阶）
O
(
c
n
)
{\displaystyle \Omicron(c^n)\!}
指数 ，有时叫作“几何 ”（阶）
O
(
n
!
)
{\displaystyle \Omicron(n!)\!}
阶乘 ，有时叫做“组合”（阶）
一些相关的渐近符号 大O是最经常使用的比较函数的渐近符号。
符号
定义
f
(
n
)
=
O
(
g
(
n
)
)
{\displaystyle f(n)=\Omicron (g(n))}
渐近上限
f
(
n
)
=
o
(
g
(
n
)
)
{\displaystyle f(n)=o(g(n))}
Asymptotically negligible渐近可忽略不计（
lim
f
(
n
)
g
(
n
)
=
0
{\displaystyle \lim{} \frac{f(n)}{g(n)} = 0}
f
(
n
)
=
Ω
(
g
(
n
)
)
{\displaystyle f(n)=\Omega(g(n))}
渐近下限（当且仅当
g
(
n
)
=
O
(
f
(
n
)
)
{\displaystyle g(n) = \Omicron(f(n))}
f
(
n
)
=
ω
(
g
(
n
)
)
{\displaystyle f(n) = \omega (g(n)) }
Asymptotically dominant渐近主导（当且仅当
g
(
n
)
=
o
(
f
(
n
)
)
{\displaystyle g(n)=o(f(n))}
f
(
n
)
=
Θ
(
g
(
n
)
)
{\displaystyle f(n) = \Theta(g(n))}
Asymptotically tight bound渐近紧约束（当且仅当
f
(
n
)
=
O
(
g
(
n
)
)
{\displaystyle f(n) = \Omicron(g(n))}
f
(
n
)
=
Ω
(
g
(
n
)
)
{\displaystyle f(n)=\Omega(g(n))}
注意 大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] . 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] . 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] . 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] . 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] .
