大O符号

(重定向自大O记法

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

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

使用

无穷大渐近

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

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


这样,針對第一個例子 ,大O符号就记下剩余的部分,写作:

 

 

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

无穷小渐近

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

  

这表示,如果 足够接近于0,那么误差 绝对值小于 的某一常数倍。

注:泰勒展开的误差余项 是关于 一个高阶无穷小量,用小o来表示,即: = ,也就是 

形式化定义

給定兩個定義在實數某子集上的關於 的函數  ,當 趨近於無窮大時,存在正实數 ,使得對於所有充分大英语sufficiently large ,都有 的絕對值小於等於 乘以 的絕對值,那麼我們就可以說,當 時,

 

也就是說,假如存在正實數 和實數 0,使得對於所有的 ,均有: 成立,我們就可以認爲, 

在很多情況下,我們會省略“當 趨近於無限大時”這個前提,而簡寫爲:

 

此概念也可以用於描述函數 在接近實數 時的行爲,通常 。當我們說,當 時,有 ,也就相當於稱,當且僅當存在正實數 和實數 ,使得對於所有的 ,均有 成立。

如果當  足夠接近時, 的值仍不爲0,這兩種定義就可以統一用上極限來表示:

當且僅當 時,有 

例子

在具体的运用中,我们不一定使用大O符号的标准定义,而是使用几条简化规则来求出关于函数 的大O表示:

  • 假如 是几项之和,那么只保留增长最快(通常是阶最高)的项,其他项省略。
  • 假如 是几项之积,那么常数(不取决于x的乘数)省略。

比如,使 ,我们想要用大O符号来简化这个函数,来描述 接近无穷大时函数的增长情况。此函数由三项相加而成,   。由于增长最快的是 这一项(因为阶最高,在x接近无穷大时,其对和的影响会大大超过其余两项),应用第一条规则,保留它而省略其他两项。对于 ,由两项相乘而得,  ;应用第二条规则, 是无关x的常数,所以省略。最后结果为 ,也即 。故有:

 ,可得:
 

我们可以将上式扩展为标准定义形式:

对任意 ,均有 ,也就是 

可以(粗略)求出  的值来验证。使 

 

 可以为13。故两者都存在。

常用的函数阶

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

符号 名称
  常数(阶,下同)
  对数
  多对数
  线性,次线性
   迭代对数
  线性对数,或对数线性、拟线性、超线性
  平方
  多项式,有时叫作“代数”(阶)
  指數,有时叫作“几何”(阶)
  阶乘,有时叫做“组合”(阶)

一些相关的渐近符号

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

符号 定义
  渐近上限
  Asymptotically negligible渐近可忽略不计( 
  渐近下限(当且仅当 
  Asymptotically dominant渐近主导(当且仅当 
  Asymptotically tight bound渐近紧约束(当且仅当  

注意

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

参看

参考文献

引用

来源

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

延伸閱讀