大O符號

大O符號（英語：Big O notation），又稱為漸進符號，是用於描述函數漸近行為的數學符號。更確切地說，它是用另一個（通常更簡單的）函數來描述一個函數數量級的漸近上界。在數學中，它一般用來刻畫被截斷的無窮級數尤其是漸近級數的剩餘項；在計算機科學中，它在分析算法複雜性的方面非常有用。

大O符號是由德國數論學家保羅·巴赫曼在其1892年的著作《解析數論》（Analytische Zahlentheorie）首先引入的。而這個記號則是在另一位德國數論學家愛德蒙·蘭道的著作中才推廣的，因此它有時又稱為蘭道符號（Landau symbols）。代表「order of ...」（……階）的大O，最初是一個大寫希臘字母「Ο」（omicron），現今用的是大寫拉丁字母「O」。

使用

無窮大漸近

大O符號在分析算法效率的時候非常有用。舉個例子，解決一個規模為$n$的問題所花費的時間（或者所需步驟的數目）可以表示為：$T(n)=4n^{2}-2n+2$。當$n$增大時，$n^{2}$項將開始占主導地位，而其他各項可以被忽略。舉例說明：當$n=500$，$4n^{2}$項是$2n$項的1000倍大，因此在大多數場合下，省略後者對表達式的值的影響將是可以忽略不計的。

進一步看，如果我們與任一其他級的表達式比較，$n^{2}$項的係數也是無關緊要的。例如：一個包含$n^{3}$或$n^{2}$項的表達式，即使$T(n)=1,000,000\cdot n^{2}$，假定$U(n)=n^{3}$，一旦$n$增長到大於1,000,000，後者就會一直超越前者（$T(1,000,000)=1,000,000^{3}=U(1,000,000)$）。

這樣，針對第一個例子$T(n)=4n^{2}-2n+2$，大O符號就記下剩餘的部分，寫作：

$T(n)\in \mathrm {O} (n^{2})$

或

$T(n)=\mathrm {O} (n^{2})$

並且我們就說該算法具有$n^{2}$階（平方階）的時間複雜度。

無窮小漸近

大O也可以用來描述數學函數估計中的誤差項。例如$e^{x}$的泰勒展開：

$e^{x}=1+x+{\frac {x^{2}}{2}}+{\hbox{O}}(x^{3})\qquad$當$x\to 0$時

這表示，如果$x$足夠接近於0，那麼誤差$e^{x}-\left(1+x+{\frac {x^{2}}{2}}\right)$的絕對值小於$x^{3}$的某一常數倍。

註：泰勒展開的誤差餘項$r_{3}(x)$是關於$x^{3}$一個高階無窮小量，用小o來表示，即：$r_{3}(x)$=$o(x^{3})$，也就是$\lim _{x\to 0}{\frac {r_{3}(x)}{x^{3}}}=0.$

形式化定義

給定兩個定義在實數某子集上的關於$x$的函數$f(x)$和$g(x)$，當$x$趨近於無窮大時，存在正實數$M$，使得對於所有充分大的$x$，都有$f(x)$的絕對值小於等於$M$乘以$g(x)$的絕對值，那麼我們就可以說，當$x\to \infty$時，

$f(x)=\mathrm {O} (g(x))$

也就是說，假如存在正實數$M$和實數$x$₀，使得對於所有的$x\geq x_{0}$，均有：$|f(x)|\leq \ M|g(x)|$成立，我們就可以認爲，$f(x)=\mathrm {O} (g(x))$。

在很多情況下，我們會省略「當$x$趨近於無限大時」這個前提，而簡寫爲：

$f(x)=\mathrm {O} (g(x))$

此概念也可以用於描述函數$f$在接近實數$a$時的行爲，通常$a=0$。當我們說，當$x\to a$時，有$f(x)=\mathrm {O} (g(x))$，也就相當於稱，當且僅當存在正實數$M$和實數$\delta$，使得對於所有的$0\leq |x-a|\leq \delta$，均有$|f(x)|\leq \ M|g(x)|$成立。

如果當$x$和$a$足夠接近時，$g(x)$的值仍不爲0，這兩種定義就可以統一用上極限來表示：

當且僅當$\limsup _{x\to a}\left|{\frac {f(x)}{g(x)}}\right|<\infty$時，有$f(x)=\mathrm {O} (g(x))$。

例子

在具體的運用中，我們不一定使用大O符號的標準定義，而是使用幾條簡化規則來求出關於函數$f$的大O表示：

• 假如$f(x)$是幾項之和，那麼只保留增長最快（通常是階最高）的項，其他項省略。
• 假如$f(x)$是幾項之積，那麼常數（不取決於x的乘數）省略。

比如，使$f(x)=6x^{4}-2x^{3}+5$，我們想要用大O符號來簡化這個函數，來描述$x$接近無窮大時函數的增長情況。此函數由三項相加而成，$6x^{4}$，$-2x^{3}$和$5$。由於增長最快的是$6x^{4}$這一項（因為階最高，在x接近無窮大時，其對和的影響會大大超過其餘兩項），應用第一條規則，保留它而省略其他兩項。對於$6x^{4}$，由兩項相乘而得，$6$和$x^{4}$；應用第二條規則，$6$是無關x的常數，所以省略。最後結果為$x^{4}$，也即$g(x)=x^{4}$。故有：

由$f(x)=\mathrm {O} (g(x))$，可得：

$6x^{4}-2x^{3}+5=O(x^{4})$

我們可以將上式擴展為標準定義形式：

對任意$x\geq x_{0}$，均有$|f(x)|\leq M|g(x)|$，也就是$6x^{4}-2x^{3}+5\leq M|x^{4}|$

可以（粗略）求出$M$和$x_{0}$的值來驗證。使$x_{0}=1$：

${\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$可以為13。故兩者都存在。

常用的函數階

下面是在分析算法的時候常見的函數分類列表。所有這些函數都處於$n$趨近於無窮大的情況下，增長得慢的函數列在上面。$c$是一個任意常數。

符號	名稱
$\mathrm {O} (1)\!$	常數（階，下同）
$\mathrm {O} (\log n)\!$	對數
$\mathrm {O} [(\log n)^{c}]\!$	多對數
$\mathrm {O} (n)\!$	線性，次線性
$\mathrm {O} (n\log ^{*}n)\!$	$\log ^{*}n$為迭代對數
$\mathrm {O} (n\log n)\!$	線性對數，或對數線性、擬線性、超線性
$\mathrm {O} (n^{2})\!$	平方
$\mathrm {O} (n^{c}),\operatorname {Integer} (c>1)$	多項式，有時叫作「代數」（階）
$\mathrm {O} (c^{n})\!$	指數，有時叫作「幾何」（階）
$\mathrm {O} (n!)\!$	階乘，有時叫做「組合」（階）

一些相關的漸近符號

大O是最經常使用的比較函數的漸近符號。

符號	定義
$f(n)=\mathrm {O} (g(n))$	漸近上限
$f(n)=o(g(n))$	Asymptotically negligible漸近可忽略不計（$\lim {}{\frac {f(n)}{g(n)}}=0$）
$f(n)=\Omega (g(n))$	漸近下限（當且僅當$g(n)=\mathrm {O} (f(n))$）
$f(n)=\omega (g(n))$	Asymptotically dominant漸近主導（當且僅當$g(n)=o(f(n))$）
$f(n)=\Theta (g(n))$	Asymptotically tight bound漸近緊約束（當且僅當$f(n)=\mathrm {O} (g(n))$且$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）.