大O符号

维基百科,自由的百科全书
跳转至: 导航搜索

注:“order”在全文中被译为“”,也可以另译为“数量级”。

大O符号(Big O notation)是用于描述函数渐近行为数学符号。更确切地说,它是用另一个(通常更简单的)函数来描述一个函数数量级渐近上界。在数学中,它一般用来刻画被截断的无穷级数尤其是渐近级数的剩余项;在计算机科学中,它在分析算法复杂性的方面非常有用。

大O符号是由德国数论学家保罗·巴赫曼(Paul Bachmann)在其1892年的著作《解析数论》(Analytische Zahlentheorie)首先引入的。而这个记号则是在另一位德国数论学家艾德蒙·朗道(Edmund Landau)的著作中才推广的,因此它有时又称为朗道符号(Landau symbols)。代表“order of ...”(……阶)的大O,最初是一个大写的希腊字母'Ο'(Omicron),现今用的是大写拉丁字母O’,但从来不是阿拉伯数字‘0’

使用[编辑]

这个符号有两种形式上很接近但迥然不同的使用方法:无穷大渐近与无穷小渐近。然而这个区别只是在运用中的而不是原则上的——除了对函数自变量的一些不同的限定, “大O”的形式定义在两种情况下都是相同的。[來源請求]

无穷大渐近[编辑]

大O符号在分析算法效率的时候非常有用。举个例子,解决一个规模为n的问题所花费的时间(或者所需步骤的数目)可以表示為:T(n)=4n^2-2n+2。当n增大时,n^2项将开始占主导地位,而其他各项可以被忽略。 举例说明:当n=5004n^2项是 2n项的1000倍大,因此在大多数场合下,省略后者对表达式的值的影响将是可以忽略不计的。

进一步看,如果我们与任一其他级的表达式比较,n^2项的系数也是无关紧要的。例如:一个包含n^3n^2项的表达式,即使 T(n)=1,000,000\cdot n^2,假定 U(n)=n^3,一旦n增长到大于1,000,000,后者就会一直超越前者(T(1,000,000)=1,000,000^3=U(1,000,000))。

这样,大O符号就记下剩余的部分,写作:

T(n)\in\Omicron(n^2)

T(n)=\Omicron(n^2)

并且我们就说该算法具有n^2阶(平方阶)的时间复杂度。

无穷小渐近[编辑]

大O也可以用来描述数学函数估计中的误差项。例如e^x泰勒展开

e^x=1+x+x^2/2+\hbox{O}(x^3)\qquadx \to 0

这表示,如果x足够接近于0,那么误差e^x - (1 + x + x^2/2)绝对值小于x^3的某一常数倍。

形式化定义[编辑]

給定兩正值函數fg,定義:

f(n)=\Omicron(g(n)),條件為:存在正實數cN,使得對於所有的n \geq N,有|f(n)| \leq |cg(n)|

上述的定義表明,當n足夠大,大過一個特定的N時,且存在一個正數c,使得|f|不大於|cg|,則fg\Omicron表示。fg的關係可以理解為g(n)f(n)的一個上界,也可以理解為f最終至多增漲的速度與g一樣快,但不會超過g的增漲速度。

常用的函数阶[编辑]

下面是在分析算法的时候常见的函数分类列表。所有这些函数都处于n趋近于无穷大的情况下,增长得慢的函数列在上面。c是一个任意常数。

符号 名称
\Omicron(1)\! 常数(阶,下同)
\Omicron(\log n)\! 对数
\Omicron[(\log n)^c]\! 多对数
\Omicron(n)\! 线性,次线性
\Omicron(n\log^*n)\! \log^*n迭代对数
\Omicron(n \log n)\! 线性对数,或对数线性、拟线性、超线性
\Omicron( n^2)\! 平方
\Omicron(n^c), \operatorname{Integer}(c>1) 多项式,有时叫作“代数”(阶)
\Omicron(c^n)\! 指数,有时叫作“几何”(阶)
\Omicron(n!)\! 阶乘,有时叫做“组合”(阶)

一些相关的渐近符号[编辑]

大O是最经常使用的比较函数的渐近符号。

符号 定义
 f(n)=\Omicron (g(n)) 渐近上限
f(n)=o(g(n)) asymptotically negligible(\lim{} \frac{f(n)}{g(n)} = 0
 f(n)=\Omega(g(n)) 渐近下限 (当且仅当 g(n) = \Omicron(f(n))
 f(n) = \omega (g(n)) asymptotically dominant(当且仅当g(n)=o(f(n))
 f(n) = \Theta(g(n)) asymptotically tight bound(当且仅当f(n) = \Omicron(g(n))f(n)=\Omega(g(n))

注意[编辑]

大O符号经常被误用:有的作者可能会使用大O符号表达大Θ符号的含义。因此在看到大O符号时应首先确定其是否为误用。

参看[编辑]

参考资料[编辑]

  • 严蔚敏,吴伟民。数据结构:C语言版。北京清华大学出版社,1996。ISBN 7-302-02368-9。1.4节 算法和算法分析,14-17页。
  • 朱青。計算機算法與程序設計。北京清华大学出版社,2009.10。ISBN 978-7-302-20267-7。1.4节 算法的複雜性分析,16-17页。