常用的函数阶[编辑]
下面是在
分析算法的时候常见的函数分类列表。所有这些函数都处于{\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符号时应首先确定其是否为误用。