大O符號(Big O notation)填抬， 又稱漸進符號侠草，是用于描述函數(shù)的漸近行為的數(shù)學符號肚菠。它是指用另一個(通常更簡單的)函數(shù)來描述一個函數(shù)數(shù)量級的漸進上界属桦。
- 由德國數(shù)論學家保羅·巴赫曼首次引入沦补，并由德國數(shù)論學家艾德蒙·朗道推廣乳蓄。
| 符號 | 名稱 |
|---|---|
| O(1) | 常量時間 |
| O(log n) | 對數(shù)時間 |
| O[(log n)c] | 多對數(shù)時間 |
| O(n) | 線性時間 |
| O(nlog* n) | 線性迭代對數(shù)時間 |
| O(nlogn) | 線性對數(shù)時間 |
| O(n2) | 平方 |
| O(nc), Integer(c>1) | 多項式時間 |
| O(cn) | 指數(shù)時間 |
| O(n!) | 階乘時間 |
在n趨于無窮大時，這些函數(shù)從上到下增長越來越快策彤。
即在用于描述時間復雜度時栓袖，隨著問題規(guī)模的增大，從上到下所需要消耗的時間越來越多店诗。
相關概念：
多項式時間(Polynomial time)即指一個問題的計算時間m(n) = O(nk ）裹刮，k為常量值。
數(shù)學家有時把“如多項式時間長的算法”視為快速計算庞瘸。
超多項式時間 即當計算規(guī)模足夠大捧弃，解題時間將大大超過任何多項式時間的問題。
相關符號：
大Ω符號：大O符號表示函數(shù)在增長到一定程度時總小于某函數(shù)的常數(shù)倍擦囊，大Ω符號與大O符號正好相反违霞，表示總大于。即：
大Θ符號是大O符號和大Ω符號的結合瞬场。即：
若
References:
