大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.

延伸阅读

编辑