「漸近符號（asymptotic notation）」包含大 O 符號（Big O notation）、大 Ω 符號（Big Omega notation）與大 θ 符號（Big Theta notation）等，可以用來表示一演算法的時間複雜度（time complexity），進而探討該演算法的好壞。

複雜度（complexity）

表示一演算法的效能，複雜度越低，代表演算法越好。

空間複雜度（space complexity）

演算法需要的記憶體空間，一般較少探討。

時間複雜度（time complexity）

演算法完成運算需要經過的時間，但這裡的「時間」不是用計時器去算幾分幾秒，主要有下列兩個原因：

1. 同一電腦多次完成相同運算，每次的耗時不一定相同。
2. 不同電腦有各自的硬體條件，完成同一運算的耗時也不會相同。

因此，探討一演算法的時間複雜度，看的是「運算元數量」，運算元越多，代表需要經過越多次的計算，時間複雜度較高。

時間複雜度範例：等差級數

計算等差級數時，可用迴圈將數字一一加總，也可直接套公式。以下比較兩方法的運算元數量：

1. 迴圈解：1+2+...+n 依序往上加，共要加總 (n–1) 次，有 (n–1) 個運算元。
2. 公式解：[(1+n)‧n]/2，不管數字多大，都只有「+」、「x」、「/」3 個運算元。

由此可知，套公式的運算元數量明顯較少、時間複雜度較低，兩者的差別將隨 n 的值逐漸變大而越來越明顯。

漸近符號（asymptotic notation）

使用一簡單的時間函式表示「代表演算法趨勢之函式」的集合。

大 O 符號（Big O notation）

最常用來探討演算法時間複雜度的指標，關注的是「最糟情況」下的運算次數，對時間複雜度影響較小的項目都不在考量範圍，因此，評估任一演算法的「Big O」時，有下列三規則：

1. 常數忽略不記，任一項次係數皆視為1
2. 較低次方者忽略不記
3. 對數底數忽略不記

以上述「等差級數」範例來說，大 O 值分別如下：

1. 迴圈解：有 (n–1) 個運算元，但較低次方的常數項 (–1) 忽略不記，因此時間複雜度為 O(n)。
2. 公式解：有 3 個運算元，但常數的值 3 不影響，因此時間複雜度為 O(1)。

「Big O」比較

對於任一演算法而言，若其「Big O」的值未隨 n 變大而急遽上升，代表它的時間複雜度低，是好的演算法。各類常見演算法的「Big O」有下列優劣關係：

較常見的「Big O」比較圖示如下：

常見「Big O」比較圖（修改自 devopedia）

「Big O」正式定義

f(n)=O(g(n))，若且唯若存在正實數 c、正實數 n₀，對於所有的 n≥n₀，可滿足 0 ≤ f(n) ≤ c·g(n)

這定義讓人看得眼花撩亂、不知所云，我們可以改用座標圖理解。
現有兩函數 f(n)、g(n) 如下：

將 g(n) 乘上一個正實數 c，會大致變成下面這樣：

對於所有的 n≥n₀，0≤f(n)≤c·g(n)，也就是只要在 n₀ 以上，f(n) 永遠比 c·g(n) 小，c·g(n) 表示 f(n) 的上界（upper bound），此時 f(n) 被定義為 O(g(n))，這個 O(g(n)) 就是「Big O」。

大 Ω 符號（Big Omega notation）

「Big Ω」跟「Big O」十分相似，但是用來表示 f(n) 的下界（lower bound），定義如下：

f(n)=Ω(g(n))，若且唯若存在正實數 c、正實數 n₀，對於所有的 n≥n₀，可滿足 0 ≤ c·g(n) ≤ f(n)

現假設有 f(n)、g(n) 如下：

將 g(n) 乘上一個正實數 c，大致變成下面這樣：

跟「Big O」不一樣的是，當 n≥n₀，f(n) 變成永遠在 c·g(n) 的「上方」，0≤c·g(n)≤f(n)，f(n) 永遠比 c·g(n) 大，c·g(n) 表示 f(n) 的下界（lower bound），此時 f(n) 被定義為 Ω(g(n))，這個 Ω(g(n)) 就是「Big Ω」。

大 θ 符號（Big Theta notation）

「Big θ」是「Big O」與「Big Ω」的綜合體，同步找出 f(n) 的上界與下界，定義如下：

f(n)=θ(g(n))，若且唯若存在正實數 c₁、正實數 c₂、正實數 n₀，對於所有的 n≥n₀，可滿足 0 ≤ c₁·g(n) ≤ f(n) ≤ c₂·g(n)

現假設有 f(n)、g(n) 如下：

將 g(x) 乘上 c₁、c₂ 後，大致變成下面這樣：

當 n≥n₀，f(n) 變成永遠在 c₂·g(n) 的「下方」、c₁·g(n) 的「上方」，0≤c₁·g(n)≤f(n)≤c₂·g(n)，f(n) 永遠在 c₁·g(n) 及 c₂·g(n) 之間，此時 f(n) 被定義為 θ(g(n))，這個 θ(g(n)) 就是「Big θ」。

「Big O」、「Big Ω」、「Big θ」比較

1. 「Big O」：只看上界，即所有時間複雜度較高的情況。
2. 「Big Ω」：只看下界，即所有時間複雜度較低的情況。
3. 「Big θ」：同時看上界與下界。

假設 f(n)=θ(n)，則三種漸近符號可同時表示如下：

在實際比較演算法的時間複雜度時，多半只會探討「所有較糟可能中的最佳情形」，也就是「上界中的最小者」，因此只會探討所有「Big O」中最小的值，否則每種演算法的「Big O」都可以取 O(nⁿ)，如此便沒有比較意義。

參考資料

1. 初學者學演算法｜談什麼是演算法和時間複雜度
2. Complexity：Asymptotic Notation(漸進符號)

*根據「國家教育研究院雙語詞彙、學術名詞暨辭書資訊網」，「asymptotic」的中文為「漸近的」，因此「asymptotic notation」翻譯應為「漸近符號」。