常用的函數階[編輯]
下面是在
分析算法的時候常見的函數分類列表。所有這些函數都處於{\displaystyle n}
趨近於無窮大的情況下,增長得慢的函數列在上面。{\displaystyle c}
是一個任意常數。
符號名稱{\displaystyle \mathrm {O} (1)\!}常數(階,下同){\displaystyle \mathrm {O} (\log n)\!}對數{\displaystyle \mathrm {O} [(\log n)^{c}]\!}多對數{\displaystyle \mathrm {O} (n)\!}線性,次線性{\displaystyle \mathrm {O} (n\log ^{*}n)\!}{\displaystyle \log ^{*}n}為迭代對數{\displaystyle \mathrm {O} (n\log n)\!}線性對數,或對數線性、擬線性、超線性{\displaystyle \mathrm {O} (n^{2})\!}平方{\displaystyle \mathrm {O} (n^{c}),\operatorname {Integer} (c>1)}1)" style="border: none; vertical-align: -0.838ex; display: inline-block; width: 21.428ex; height: 2.843ex;">指數,有時叫作“幾何”(階){\displaystyle \mathrm {O} (c^{n})\!}多項式,有時叫作“代數”(階){\displaystyle \mathrm {O} (n!)\!}階乘,有時叫做“組合”(階)
一些相關的漸近符號[編輯]
大O是最經常使用的比較函數的漸近符號。
符號定義{\displaystyle f(n)=\mathrm {O} (g(n))}漸近上限{\displaystyle f(n)=o(g(n))}asymptotically negligible 漸近可忽略不計({\displaystyle \lim {}{\frac {f(n)}{g(n)}}=0}){\displaystyle f(n)=\Omega (g(n))}漸近下限 (當且僅當{\displaystyle g(n)=\mathrm {O} (f(n))}){\displaystyle f(n)=\omega (g(n))}asymptotically dominant 漸近主導(當且僅當{\displaystyle g(n)=o(f(n))}){\displaystyle f(n)=\Theta (g(n))}asymptotically tight bound 漸近緊約束(當且僅當{\displaystyle f(n)=\mathrm {O} (g(n))}且{\displaystyle f(n)=\Omega (g(n))})
注意[編輯]
大O符號經常被誤用:有的作者可能會使用大O符號表達
大Θ符號的含義。因此在看到大O符號時應首先確定其是否為誤用。