万维百科

大O符号

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

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

使用

无穷大渐近

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

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


这样,针对第一个例子, 大O符号就记下剩余的部分,写作:

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

无穷小渐近

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

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

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

形式化定义

给定两个定义在实数某子集上的关于的函数,当趋近于无穷大时,当且仅当存在正常量,使得对于所有足够大(sufficiently_large)的,都有的绝对值小于等于乘以的绝对值,那么我们就可以说,当时,

也就是说,假如当且仅当存在正实数和实数0,使得对于所有的,均有:成立,我们就可以认为,

在很多情况下,我们会省略“当趋近于无限大时”这个前提,而简写为:

此概念也可以用于描述函数在接近实数时的行为,通常。当我们说,当时,有,也就相当于称,当且仅当存在正实数和实数,使得对于所有的,均有成立。

如果当足够接近(sufficiently_close)时,的值仍不为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.

延伸阅读

  • Hardy, G. H. Orders of Infinity: The 'Infinitärcalcül' of Paul du Bois-Reymond. Cambridge University Press. 1910.
  • Knuth, Donald. 1.2.11: Asymptotic Representations. Fundamental Algorithms. The Art of Computer Programming 1 3rd. Addison–Wesley. 1997. ISBN 0-201-89683-4.
  • Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford. 3.1: Asymptotic notation. Introduction to Algorithms 2nd. MIT Press and McGraw–Hill. 2001. ISBN 0-262-03293-7.
  • Sipser, Michael. Introduction to the Theory of Computation. PWS Publishing. 1997: 226–228. ISBN 0-534-94728-X.
  • Avigad, Jeremy; Donnelly, Kevin. Formalizing O notation in Isabelle/HOL (PDF). International Joint Conference on Automated Reasoning. 2004. doi:10.1007/978-3-540-25984-8_27.
  • Black, Paul E. Black, Paul E. , 编. big-O notation. Dictionary of Algorithms and Data Structures. U.S. National Institute of Standards and Technology. 11 March 2005 [December 16, 2006]. (原始内容存档于2019-05-20).
  • Black, Paul E. Black, Paul E. , 编. little-o notation. Dictionary of Algorithms and Data Structures. U.S. National Institute of Standards and Technology. 17 December 2004 [December 16, 2006].
  • Black, Paul E. Black, Paul E. , 编. Ω. Dictionary of Algorithms and Data Structures. U.S. National Institute of Standards and Technology. 17 December 2004 [December 16, 2006].
  • Black, Paul E. Black, Paul E. , 编. ω. Dictionary of Algorithms and Data Structures. U.S. National Institute of Standards and Technology. 17 December 2004 [December 16, 2006].
  • Black, Paul E. Black, Paul E. , 编. Θ. Dictionary of Algorithms and Data Structures. U.S. National Institute of Standards and Technology. 17 December 2004 [December 16, 2006].

本页面最后更新于2021-07-06 11:13,点击更新本页查看原网页。台湾为中国固有领土,本站将对存在错误之处的地图、描述逐步勘正。

本站的所有资料包括但不限于文字、图片等全部转载于维基百科(wikipedia.org),遵循 维基百科:CC BY-SA 3.0协议

万维百科为维基百科爱好者建立的公益网站,旨在为中国大陆网民提供优质内容,因此对部分内容进行改编以符合中国大陆政策,如果您不接受,可以直接访问维基百科官方网站


顶部

如果本页面有数学、化学、物理等公式未正确显示,请使用火狐或者Safari浏览器