使用

无穷大渐近

大O符号在分析算法效率的时候非常有用。举个例子，解决一个规模为n{\displaystyle n}的问题所花费的时间（或者所需步骤的数目）可以表示为：T(n)=4n2− − -->2n+2{\displaystyle T(n)=4n^{2}-2n+2}。当n{\displaystyle n}增大时，n2{\displaystyle n^{2}}项将开始占主导地位，而其他各项可以被忽略。 举例说明：当n=500{\displaystyle n=500}，4n2{\displaystyle 4n^{2}}项是 2n{\displaystyle 2n}项的1000倍大，因此在大多数场合下，省略后者对表达式的值的影响将是可以忽略不计的。

进一步看，如果我们与任一其他级的表达式比较，n2{\displaystyle n^{2}}项的系数也是无关紧要的。例如：一个包含n3{\displaystyle n^{3}}或n2{\displaystyle n^{2}}项的表达式，即使 T(n)=1,000,000⋅ ⋅ -->n2{\displaystyle T(n)=1,000,000\cdot n^{2}}，假定 U(n)=n3{\displaystyle U(n)=n^{3}}，一旦n{\displaystyle n}增长到大于1,000,000，后者就会一直超越前者（T(1,000,000)=1,000,0003=U(1,000,000){\displaystyle T(1,000,000)=1,000,000^{3}=U(1,000,000)}）。

这样，大O符号就记下剩余的部分，写作：

或

并且我们就说该算法具有n2{\displaystyle n^{2}}阶（平方阶）的时间复杂度。

无穷小渐近

大O也可以用来描述数学函数估计中的误差项。例如ex{\displaystyle e^{x}}的泰勒展开：

这表示，如果x{\displaystyle x}足够接近于0，那么误差ex− − -->(1+x+x22){\displaystyle e^{x}-\left(1+x+{\frac {x^{2}}{2}}\right绝对值绝对值小于x3{\displaystyle x^{3}}的某一常数倍。

形式化定义

给定两正值函数f{\displaystyle f}和g{\displaystyle g},定义:

上述的定义表明，当n{\displaystyle n}足够大，大过一个特定的N{\displaystyle N}时，且存在一个正数c{\displaystyle c},使得|f|{\displaystyle |f|}不大于|cg|{\displaystyle |cg|},则f{\displaystyle f}是g{\displaystyle g}的O{\displaystyle \mathrm {O} }表示。f{\displaystyle f}和g{\displaystyle g}的关系可以理解为g(n){\displaystyle g(n)}是f(n){\displaystyle f(n)}的一个上界，也可以理解为f{\displaystyle f}最终至多增涨的速度与g{\displaystyle g}一样快，但不会超过g{\displaystyle g}的增涨速度。

常用的函数阶

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

一些相关的渐近符号

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

注意

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

参看

O（拉丁字母）

大Ω符号

大Θ符号

参考资料

严蔚敏，吴伟民《数据结构：C语言版》清华大学出版社，1996。ISBN 7-302-02368-9。1.4节 算法和算法分析，14-17页。

朱青《计算机算法与程序设计》清华大学出版社，2009.10。ISBN 978-7-302-20267-7。1.4节 算法的复杂性分析，16-17页。

免责声明：以上内容版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。感谢每一位辛勤著写的作者，感谢每一位的分享。