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