大O符號

大O符號（Big O notation），又稱為漸近符號，是用於描述函數漸近行為的數學符號。更確切地說，它是用另一個（通常更簡單的）函數來描述一個函數數量級的漸近上界。在數學中，一般是用來刻畫被截斷的無窮級數尤其是漸近級數的剩餘項；在電腦科學中，用來分析演算法複雜性的方面非常有用。

大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$和實數$x$0，使得對於所有的$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| < \infty$時，有$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\\ <pre> &\le 6x^4 + 2x^4 + 5x^4\\ &\le 13x^4\end{align}$$

故$M$可以為13。故兩者都存在。

## 常用的函數階

下面是在分析演算法的時候常見的函數分類列表。所有這些函數都處於$n$趨近於無窮大的情況下，增長得慢的函數列在上面。$c$是一個任意常數。

符號｜名稱

$\Omicron(1)\!$｜常數（階，下同）

$\Omicron(\log n)\!$｜對數

$\Omicron[(\log n)^c]\!$｜多對數

$\Omicron(n)\!$｜線性，次線性

$\Omicron(n\log^*n)\!$｜$\log^*n$為迭代對數

$\Omicron(n \log n)\!$｜線性對數，或對數線性、擬線性、超線性

$\Omicron( n^2)\!$｜平方

$\Omicron(n^c), \operatorname{Integer}(c>1)$｜多項式，有時叫作「代數」（階）

$\Omicron(c^n)\!$｜指數，有時叫作「幾何」（階）

$\Omicron(n!)\!$｜階乘，有時叫做「組合」（階）

## 一些相關的漸近符號

大O是最經常使用的比較函數的漸近符號。

符號｜定義

$f(n)=\Omicron (g(n))$｜漸近上限

$f(n)=o(g(n))$｜Asymptotically negligible漸近可忽略不計（$\lim{} \frac{f(n)}{g(n)} = 0$）

$f(n)=\Omega(g(n))$｜漸近下限（若且唯若$g(n) = \Omicron(f(n))$）

$f(n) = \omega (g(n))$｜Asymptotically dominant漸近主導（若且唯若$g(n)=o(f(n))$）

$f(n) = \Theta(g(n))$｜Asymptotically tight bound漸近緊約束（若且唯若$f(n) = \Omicron(g(n))$且$f(n)=\Omega(g(n))$）

## 注意

大O符號經常被誤用：有的作者可能會使用大O符號表達大Θ符號的含義。因此在看到大O符號時應首先確定其是否為誤用。