大O符號

大O符號是由德國數論學家保羅·巴赫曼（Paul Bachmann）在其1892年的著作《解析數論》（Analytische Zahlentheorie）首先引入的。而這個記號則是在另一位德國數論學家艾德蒙·朗道（Edmund Landau）的著作中才推廣的，因此它有時又稱為朗道符號（Landau symbol）。代表“order of ...”（……階）的大O，最初是一個大寫的希臘字母'Ο'（Omicron），現今用的是英文大寫字母'O'，但從來不是阿拉伯數字'0'。

這個符號有兩種形式上很接近但迥然不同的使用方法：無窮大漸近與無窮小漸近。然而這個區別只是在運用中的而不是原則上的——除了對函數自變數的一些不同的限定，“大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,000n^2;，假定 U(n) = n^3;，一旦 n 增長到大於1,000,000，後者就會一直超越前者(T(1,000,000) = 1,000,000^3; = U(1,000,000))。

這樣，大O符號就記下剩餘的部分，寫作：

T(n）∈O(n^2)

並且我們就說該演演算法具有 2階的時間複雜度。

大O也可以用來描述數學函數估計中的誤差項。例如：

e^x=1+x+x^2/2+O(x^3) 當 x→0 時

這表示，如果 x 足夠接近於0，那麼誤差（e^x− (1 + x + x^2 / 2)的差）的絕對值小於 x^3的某一常數倍。

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