大O符号（），又稱為漸近符號，是用于描述函数渐近行为的数学符号。更确切地说，它是用另一个（通常更简单的）函数来描述一个函数数量级的渐近上界。在数学中，一般是用来刻画被截断的无穷级数尤其是渐近级数的剩余项；在计算机科学中，用来分析算法复杂性的方面非常有用。
大O符号是由德国数论学家保罗·巴赫曼在其1892年的著作《解析数论》（Analytische Zahlentheorie）首先引入的。而这个记号则是在另一位德国数论学家愛德蒙·蘭道的著作中才推广的，因此会有时又称为蘭道符号（Landau symbols）。代表“order of ...”（……阶）的大O，最初是一个大写希腊字母“Ο”（omicron），现今用的是大写拉丁字母“O”。
使用
无穷大渐近
大O符号在分析算法效率的时候非常有用。举个例子，解决一个规模为n的问题所花费的时间（或者所需步骤的数目）可以表示為：T(n)=4n^2-2n+2。当n增大时，n^2项将开始占主导地位，而其他各项可以被忽略。举例说明：当n=500，4n^2项是2n项的1000倍大，因此在大多数场合下，省略后者对表达式的值的影响将是可以忽略不计的。
进一步看，如果我们与任一其他级的表达式比较，n^2项的系数也是无关紧要的。例如：一个包含n^3或n^2项的表达式，即使T(n)=1,000,000\cdot n^2，假定U(n)=n^3，一旦n增长到大于1,000,000，后者就会一直超越前者（T(1,000,000)=1,000,000^3=U(1,000,000)）。
这样，針對第一個例子T(n)=4n^2-2n+2，大O符号就记下剩余的部分，写作：
:T(n)\in\Omicron(n^2)
或
:T(n)=\Omicron(n^2)
并且我们就说该算法具有n^2阶（平方阶）的时间复杂度。
无穷小渐近
大O也可以用来描述数学函数估计中的误差项。例如e^x的泰勒展开：
:e^x=1+x+\frac{x^2}{2}+\hbox{O}(x^3)\qquad当x \to 0时
这表示，如果x足够接近于0，那么误差e^x - \left(1 + x + \frac{x^2}{2}\right)的绝对值小于x^3的某一常数倍。
注：泰勒展开的误差余项r_3(x)是关于x^3一个高阶无穷小量，用小o来表示，即：r_3(x)=o(x^3)，也就是\lim_{x \to 0} \frac{r_3(x)}{x^3}=0.
形式化定义
給定兩個定義在實數某子集上的關於x的函數f(x)和g(x)，當x趨近於無窮大時，存在正实數M，使得對於所有充分大的x，都有f(x)的絕對值小於等於M乘以g(x)的絕對值，那麼我們就可以說，當x \to \infty時，
:f(x)=\Omicron(g(x))
也就是說，假如存在正實數M和實數x0，使得對於所有的x \ge x_0，均有：|f(x)| \le \ M |g(x)|成立，我們就可以認爲，f(x)=\Omicron(g(x))。
在很多情況下，我們會省略“當x趨近於無限大時”這個前提，而簡寫爲：
:f(x)=\Omicron(g(x))
此概念也可以用於描述函數f在接近實數a時的行爲，通常a = 0。當我們說，當x \to a時，有f(x)=\Omicron(g(x))，也就相當於稱，當且僅當存在正實數M和實數\delta，使得對於所有的0 \le |x - a| \le \delta，均有|f(x)| \le \ M |g(x)|成立。
如果當x和a足夠接近時，g(x)的值仍不爲0，這兩種定義就可以統一用上極限來表示：
:當且僅當\limsup_{x\to a} \left|\frac{f(x)}{g(x)}\right| 時，有f(x)=\Omicron(g(x))。
例子
在具体的运用中，我们不一定使用大O符号的标准定义，而是使用几条简化规则来求出关于函数f的大O表示：
- 假如f(x)是几项之和，那么只保留增长最快（通常是阶最高）的项，其他项省略。
- 假如f(x)是几项之积，那么常数（不取决于x的乘数）省略。
比如，使f(x) = 6x^4 - 2x^3 + 5，我们想要用大O符号来简化这个函数，来描述x接近无穷大时函数的增长情况。此函数由三项相加而成，6x^4，-2x^3和5。由于增长最快的是6x^4这一项（因为阶最高，在x接近无穷大时，其对和的影响会大大超过其余两项），应用第一条规则，保留它而省略其他两项。对于6x^4，由两项相乘而得，6和x^4；应用第二条规则，6是无关x的常数，所以省略。最后结果为x^4，也即g(x) = x^4。故有：
:由f(x) = \Omicron(g(x))，可得：
:6x^4 - 2x^3 + 5 = O(x^4)
我们可以将上式扩展为标准定义形式：
:对任意x \ge x_0，均有|f(x)| \le M|g(x)|，也就是6x^4 - 2x^3 + 5 \le M|x^4|
可以（粗略）求出M和x_0的值来验证。使x_0=1：
:\begin{align}|6x^4 - 2x^3 + 5| &\le 6x^4 + |2x^3| + 5\\
&\le 6x^4 + 2x^4 + 5x^4\\
&\le 13x^4\end{align}
故M可以为13。故两者都存在。
常用的函数阶
下面是在分析算法的时候常见的函数分类列表。所有这些函数都处于n趋近于无穷大的情况下，增长得慢的函数列在上面。c是一个任意常数。
一些相关的渐近符号
大O是最经常使用的比较函数的渐近符号。
注意
大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.
延伸閱讀
*
*
*
*
*
*
*
*
*
*
评论 (0)