大O符号

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

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

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

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

这样，针对第一个例子${\displaystyle T(n)=4n^2-<!--\; -\; -->2n+2}$, 大O符号就记下剩余的部分，写作：

或

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

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

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

注：泰勒展开的误差余项${\displaystyle r_3(x)}$是关于${\displaystyle x^3}$一个高阶无穷小量，用小o来表示，即：${\displaystyle r_3(x)}$=${\displaystyle o(x^3)}$，${\displaystyle \underset{x\to <!--\; \to \; -->0}{lim}{\displaystyle \frac{r_3(x)}{x^3}=0}}$

给定两个定义在实数某子集上的关于${\displaystyle x}$的函数${\displaystyle f(x)}$和${\displaystyle g(x)}$，当${\displaystyle x}$趋近于无穷大时，当且仅当存在正常量${\displaystyle M}$，使得对于所有足够大（sufficiently_large）的${\displaystyle x}$，都有${\displaystyle f(x)}$的绝对值小于等于${\displaystyle M}$乘以${\displaystyle g(x)}$的绝对值，那么我们就可以说，当${\displaystyle x\to <!--\; \to \; -->\mathrm{\infty <!--\; \infty \; -->}}$时，

也就是说，假如当且仅当存在正实数${\displaystyle M}$和实数${\displaystyle x}$₀，使得对于所有的${\displaystyle x\ge <!--\; \ge \; -->x_0}$，均有：${\displaystyle |f(x)|\le <!--\; \le \; -->M|g(x)|}$成立，我们就可以认为，${\displaystyle f(x)=\mathrm{O}(g(x))}$。

在很多情况下，我们会省略“当${\displaystyle x}$趋近于无限大时”这个前提，而简写为：

此概念也可以用于描述函数${\displaystyle f}$在接近实数${\displaystyle a}$时的行为，通常${\displaystyle a=0}$。当我们说，当${\displaystyle x\to <!--\; \to \; -->a}$时，有${\displaystyle f(x)=\mathrm{O}(g(x))}$，也就相当于称，当且仅当存在正实数${\displaystyle M}$和实数${\displaystyle \mathrm{\delta <!--\; \delta \; -->}}$，使得对于所有的${\displaystyle 0\le <!--\; \le \; -->|x-<!--\; -\; -->a|\le <!--\; \le \; -->\mathrm{\delta <!--\; \delta \; -->}}$，均有${\displaystyle |f(x)|\le <!--\; \le \; -->M|g(x)|}$成立。

如果当${\displaystyle x}$和${\displaystyle a}$足够接近（sufficiently_close）时，${\displaystyle g(x)}$的值仍不为0，这两种定义就可以统一用上极限来表示：

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

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

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

可以（粗略）求出${\displaystyle M}$和${\displaystyle x_0}$的值来验证。使${\displaystyle x_0=1}$：

故${\displaystyle M}$可以为13。故两者都存在。

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

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

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