大O符号
大O符号
大O符号（），又称为渐进符号，是用于描述函数渐近行为的数学符号。更确切地说，它是用另一个（通常更简单的）函数来描述一个函数数量级的渐近上界。在数学中，它一般用来刻画被截断的无穷级数尤其是渐近级数的剩余项；在计算机科学中，它在分析算法复杂性的方面非常有用。
大O符号是由德国数论学家保罗·巴赫曼在其1892年的著作《解析数论》（"Analytische Zahlentheorie"）首先引入的。而这个记号则是在另一位德国数论学家爱德蒙·兰道的著作中才推广的，因此它有时又称为兰道符号（Landau symbols）。代表“order of ...”（……阶）的大O，最初是一个大写希腊字母“Ο”（omicron），现今用的是大写拉丁字母“O”。
使用.
无穷大渐近.
大O符号在分析算法效率的时候非常有用。举个例子，解决一个规模为formula_1的问题所花费的时间（或者所需步骤的数目）可以表示为：formula_2。当formula_1增大时，formula_4项将开始占主导地位，而其他各项可以被忽略。举例说明：当formula_5，formula_6项是formula_7项的1000倍大，因此在大多数场合下，省略后者对表达式的值的影响将是可以忽略不计的。
进一步看，如果我们与任一其他级的表达式比较，formula_4项的系数也是无关紧要的。例如：一个包含formula_9或formula_4项的表达式，即使formula_11，假定formula_12，一旦formula_1增长到大于1,000,000，后者就会一直超越前者（formula_14）。
这样，针对第一个例子formula_2，大O符号就记下剩余的部分，写作：
formula_16
或
formula_17
并且我们就说该算法具有formula_4阶（平方阶）的时间复杂度。
无穷小渐近.
大O也可以用来描述数学函数估计中的误差项。例如formula_19的泰勒展开：
formula_20当formula_21时
这表示，如果formula_22足够接近于0，那么误差formula_23的绝对值小于formula_24的某一常数倍。
注：泰勒展开的误差余项formula_25是关于formula_24一个高阶无穷小量，用小o来表示，即：formula_25=formula_28，也就是formula_29
形式化定义.
给定两个定义在实数某子集上的关于formula_22的函数formula_31和formula_32，当formula_22趋近于无穷大时，存在正实数formula_34，使得对于所有的formula_22，都有formula_31的绝对值小于等于formula_34乘以formula_32的绝对值，那么我们就可以说，当formula_39时，
formula_40
也就是说，假如存在正实数formula_34和实数formula_220，使得对于所有的formula_43，均有：formula_44成立，我们就可以认为，formula_40。
在很多情况下，我们会省略“当formula_22趋近于无限大时”这个前提，而简写为：
formula_40
此概念也可以用于描述函数formula_48在接近实数formula_49时的行为，通常formula_50。当我们说，当formula_51时，有formula_40，也就相当于称，当且仅当存在正实数formula_34和实数formula_54，使得对于所有的formula_55，均有formula_44成立。
如果当formula_22和formula_49足够接近时，formula_32的值仍不为0，这两种定义就可以统一用上极限来表示：
当且仅当formula_60时，有formula_40。
例子.
在具体的运用中，我们不一定使用大O符号的标准定义，而是使用几条简化规则来求出关于函数formula_48的大O表示：
比如，使formula_65，我们想要用大O符号来简化这个函数，来描述formula_22接近无穷大时函数的增长情况。此函数由三项相加而成，formula_67，formula_68和formula_69。由于增长最快的是formula_67这一项（因为阶最高，在x接近无穷大时，其对和的影响会大大超过其余两项），应用第一条规则，保留它而省略其他两项。对于formula_67，由两项相乘而得，formula_72和formula_73；应用第二条规则，formula_72是无关x的常数，所以省略。最后结果为formula_73，也即formula_76。故有：
由formula_77，可得：
formula_78
我们可以将上式扩展为标准定义形式：
对任意formula_43，均有formula_80，也就是formula_81
可以（粗略）求出formula_34和formula_83的值来验证。使formula_84：
formula_85
故formula_34可以为13。故两者都存在。
常用的函数阶.
下面是在分析算法的时候常见的函数分类列表。所有这些函数都处于formula_1趋近于无穷大的情况下，增长得慢的函数列在上面。formula_88是一个任意常数。
一些相关的渐近符号.
大O是最经常使用的比较函数的渐近符号。
注意.
大O符号经常被误用：有的作者可能会使用大O符号表达大Θ符号的含义。因此在看到大O符号时应首先确定其是否为误用。
参考文献.
来源.
延伸阅读.
本站由爱斯园团队开发维护，感谢那些提出宝贵意见和打赏的网友，没有你们的支持，网站不可能发展到今天，
继往开来，善终如始，我们将继续砥砺前行。
Copyright ©2014 iissy.com, All Rights Reserved.