大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 \mathrm {O} (n^{2})}
或
T
(
n
)
=
O
(
n
2
)
{\displaystyle T(n)=\mathrm {O} (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 \lim _{x\to 0}{\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)=\mathrm {O} (g(x))}
也就是說，假如存在正實數
M
{\displaystyle M}
x
{\displaystyle x}
0 ，使得對於所有的
x
≥
x
0
{\displaystyle x\geq x_{0}}
|
f
(
x
)
|
≤
M
|
g
(
x
)
|
{\displaystyle |f(x)|\leq \ M|g(x)|}
f
(
x
)
=
O
(
g
(
x
)
)
{\displaystyle f(x)=\mathrm {O} (g(x))}
在很多情況下，我們會省略「當
x
{\displaystyle x}
f
(
x
)
=
O
(
g
(
x
)
)
{\displaystyle f(x)=\mathrm {O} (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)=\mathrm {O} (g(x))}
當且僅當 存在正實數
M
{\displaystyle M}
δ
{\displaystyle \delta }
0
≤
|
x
−
a
|
≤
δ
{\displaystyle 0\leq |x-a|\leq \delta }
|
f
(
x
)
|
≤
M
|
g
(
x
)
|
{\displaystyle |f(x)|\leq \ 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)=\mathrm {O} (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)=\mathrm {O} (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\geq x_{0}}
|
f
(
x
)
|
≤
M
|
g
(
x
)
|
{\displaystyle |f(x)|\leq M|g(x)|}
6
x
4
−
2
x
3
+
5
≤
M
|
x
4
|
{\displaystyle 6x^{4}-2x^{3}+5\leq 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{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
{\displaystyle M}
下面是在分析算法 的時候常見的函數分類列表。所有這些函數都處於
n
{\displaystyle n}
c
{\displaystyle c}
符號
名稱
O
(
1
)
{\displaystyle \mathrm {O} (1)\!}
常數 （階，下同）
O
(
log
n
)
{\displaystyle \mathrm {O} (\log n)\!}
對數
O
[
(
log
n
)
c
]
{\displaystyle \mathrm {O} [(\log n)^{c}]\!}
多對數
O
(
n
)
{\displaystyle \mathrm {O} (n)\!}
線性 ，次線性
O
(
n
log
∗
n
)
{\displaystyle \mathrm {O} (n\log ^{*}n)\!}
log
∗
n
{\displaystyle \log ^{*}n}
迭代對數
O
(
n
log
n
)
{\displaystyle \mathrm {O} (n\log n)\!}
線性對數，或對數線性、擬線性、超線性
O
(
n
2
)
{\displaystyle \mathrm {O} (n^{2})\!}
平方
O
(
n
c
)
,
Integer
(
c
>
1
)
{\displaystyle \mathrm {O} (n^{c}),\operatorname {Integer} (c>1)}
多項式 ，有時叫作「代數」（階）
O
(
c
n
)
{\displaystyle \mathrm {O} (c^{n})\!}
指數 ，有時叫作「幾何 」（階）
O
(
n
!
)
{\displaystyle \mathrm {O} (n!)\!}
階乘 ，有時叫做「組合」（階）
大O是最經常使用的比較函數的漸近符號。
符號
定義
f
(
n
)
=
O
(
g
(
n
)
)
{\displaystyle f(n)=\mathrm {O} (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)=\mathrm {O} (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)=\mathrm {O} (g(n))}
f
(
n
)
=
Ω
(
g
(
n
)
)
{\displaystyle f(n)=\Omega (g(n))}
大O符號經常被誤用：有的作者可能會使用大O符號表達大Θ符號 的含義。因此在看到大O符號時應首先確定其是否為誤用。
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）.
![{\displaystyle \mathrm {O} [(\log n)^{c}]\!}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1b59e14bd1ca3550ec4f649c41786884bbe368b5)
