大O符號

大O符號

大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!)階乘,有時叫做“組合”(階)