大O符号

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

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

 使用 

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

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

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

或

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

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

当时

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

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

 形式化定义 

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

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

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

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

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

當且僅當時，有。

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

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

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

由，可得：

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

对任意，均有，也就是

可以（粗略）求出和的值来验证。使：

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

 常用的函数阶 

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

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

 一些相关的渐近符号 

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

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

注意
大O符号经常被误用：有的作者可能会使用大O符号表达大Θ符号的含义。因此在看到大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.

延伸閱讀












Category:算法分析
Category:數學表示法
Category:数学符号
Category:渐近分析