大O符號

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

基本介紹

• 中文名：大O符號
• 外文名：Big O notation
• 用於：描述函式漸進行為
• 性質：數學符號
• 提出文獻：(德) 保羅·巴赫曼《解析數論》

朗道符號

大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 是一個任意常數。

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