🔍

大O表示法

大O符号,又称为渐进符号,是用于描述函数渐近行为的数学符号。更确切地说,它是用另一个函数来描述一个函数数量级的渐近上界。在数学中,它一般用来刻画被截断的无穷级数尤其是渐近级数的剩余项;在计算机科学中,它在分析算法复杂性的方面非常有用。 大O符号是由德国数论学家保罗·巴赫曼在其1892年的著作《解析数论》首先引入的。维基百科

无穷大渐近

大O符号在分析算法效率的时候非常有用。举个例子,解决一个规模为 n 的问题所花费的时间(或者所需步骤的数目)可以表示为:T(n)=4n^2^-2n+2 。当 n 增大时,二次项项将开始占主导地位,而其他各项可以被忽略。所以,可得出结论如下。

使用大 O 符号可以把 T(n)=4n^2^-2n+2 表示为 T(n) ∈ O(n^2^)T(n) = O(n^2^) ,并且我们就说该算法具有 n^2^ 阶(平方阶)的时间复杂度。

数学定义

当且仅当存在正实数 M 和实数 x~0~ ,使得对于所有的 x ≥ x~0~ ,均有 |T(x)| ≤ M|f(x)| 成立,我们就可以认为, T(x) = O(f(x))

例如,如果 T(x) = 4x^2^-2x+2 ,则可以用大 O 表示法表示为 T(x) = O(x^2^) 。粗略的推到过程如下。

令 x~0~ = 1 ,对于所有的 x ≥ x~0~ ,有 4x^2^-2x+2 ≤ 4x^2^+2x+2 = |4x^2^+2x+2 | ≤ 4x^2^ = |4x^2^| ,故存在实数 M = 4 使得 |T(x)| ≤ M|f(x)| 成立 ,毕。

常用函数阶

符号名称
O(1)常数
O(x)线性
O(c^x^)指数
O(logx)对数
O(xlogx)线性对数
O(x^c^),其中 c ∈ N^+^幂次
O(!x)阶乘

函数图像

也就是高中学的那几个函数图像,如下所示: