大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] .
