時間複雜度

發佈於 2026-01-01 更新於 2026-01-01 約 2782 字預計閱讀 6 分鐘次閱讀

https://raw.githubusercontent.com/Josh-test-lab/website-assets-repository/refs/heads/main/posts/time%20complexity/cover%20image.webp

封面圖片由 ChatGPT 生成。

時間複雜度（time complexity）是用來描述演算法在執行過程中，隨著輸入規模增大，其所需要的運算時間如何成長。由於不同電腦設備的處理效能、硬體架構與系統環境皆有所差異，若單純以實際執行時間作為演算法比較的依據，往往難以得到具有代表性且可移植的結論。因此，時間複雜度通常以「基本操作的執行次數」作為衡量標準，並使用漸進複雜度（asymptotic complexity）分析演算法的效率，從而建立一個與硬體無關且可通用的性能評估方式。

漸進符號

在分析演算法時，我們通常假設每一步基本操作所需的時間相同。透過時間複雜度分析，我們能預測程式在大規模輸入下的執行效率，並提供比較不同演算法效率的標準，同時協助進行效能優化與資源規劃。漸進符號（asymptotic notation）是描述時間複雜度的主要工具，其中以大 $O$ 符號最為常見。

以下以多項式函數 $$ T(n) = 4n^2 - 2n + 2 $$ 為例，其時間複雜度可分為以下幾類：

大 $O$ 符號

大 $O$ 符號（Big-O notation）描述的是函數的「漸進上界」，代表當輸入規模足夠大時，函數的成長率不會超過某個上界，通常在演算法分析中被用於表示最壞情況的時間複雜度。其定義如下：

若存在常數 $c > 0$ 與 $n_0 > 0$ ，以及函數 $f$ 和 $g$ ，使得 $$ 0 \le f(n) \le c \cdot g(n), \quad \forall n \ge n_0, $$ 則 $$ f(n) \in O(g(n)) $$ 也可表示為 $$ f(n) = O(g(n)), $$ 說明函數 $f$ 的時間複雜度上界為 $O(g(n))$ 。

以先前的例子 $T(n)$ 來說，我們可以得到 $$ T(n) \in O(4n^2 - 100n + 2). $$

然而，在漸進分析中，我們關注的是當 $n$ 足夠大時，哪個項主導整體成長。以 $T(n)$ 為例，以下表格呈現當 $n$ 增長時，各項的計算結果。

$n$	$4n^2$	$- 2n$	$2$
1	4	-2	2
10	400	-20	2
100	40000	-200	2

由上表可知，當 $n$ 增加時，最高次方項的增長幅度最巨，其量級會遠超於其他項，且漸進成長率與係數無關。因此，大 $O$ 符號通常簡化為最高次方項，如 $$ T(n) = O(n^2). $$

大 $\Omega$ 符號

大 $\Omega$ 符號（Big-Omega notation）描述的是函數的「漸進下界」，代表函數成長率不會低於某個下界，通常用於表達最佳情況的時間複雜度。其定義如下：

若存在常數 $c > 0$ 與 $n_0 > 0$ 以及函數 $f$ 和 $g$，使得 $$ 0 \le c \cdot g(n) \le f(n), \quad \forall n \ge n_0, $$ 則 $$ f(n) \in \Omega(g(n)) $$ 或 $$ f(n) = \Omega(g(n)). $$

對於前述例子 $T(n)$ ，由於二次項主導整體成長，我們可以找到常數 $c > 0$（例如 $c = 1$）使得 $$ c \cdot n^2 \le 4n^2 - 2n + 2, \quad \forall n \ge n_0, $$

因此， $T(n)$ 的漸進下界可表示為 $$ T(n) = \Omega(n^2). $$

大 $\Theta$ 符號

大 $\Theta$ 符號（Big-Theta notation）描述的是函數的「漸進緊密界線」（tight bound），用來表示與 $g(n)$ 具有相同成長率的函數集合。其定義如下：

若存在常數 $c_1 > 0$ 與 $c_2 > 0$ 及 $n_0 > 0$ ，使得 $$ 0 \le c_1 \cdot g(n) \le f(n) \le c_2 \cdot g(n), \quad \forall n \ge n_0, $$ 則 $$ f(n) \in \Theta(g(n)) \quad \text{或} \quad f(n) = \Theta(g(n)). $$

換句話說， $f(n)$ 的漸進上界與下界同時由 $g(n)$ 控制，因此 $$ f(n) = O(g(n)) \quad \text{且} \quad f(n) = \Omega(g(n)). $$

對於前述例子 $T(n)$ ，因為 $$ T(n) = O(n^2) \quad \text{且} \quad T(n) = \Omega(n^2), $$ 故 $$ T(n) = \Theta(n^2). $$

大 $\Theta$ 符號指出，$T(n)$ 的漸進成長率恰為二次方級別，既不會低於，也不會高於 $n^2$ 的量級。

常見的時間複雜度

在分析演算法時，不同的演算法會有不同的時間複雜度。以下列出常見的時間複雜度及其描述：

複雜度	名稱	描述	常見範例
$O(1)$	常數時間	執行時間不隨輸入大小變化	訪問陣列元素、哈希表查詢
$O(\log n)$	對數時間	每步將問題規模縮小（分治策略）	二分搜尋
$O(n)$	線性時間	需檢查所有資料一次	遍歷陣列、計算總和
$O(n \log n)$	線性對數時間	高效排序	合併排序法、堆積排序法
$O(n^2)$	平方時間	雙層迴圈操作	氣泡排序法、選擇排序法
$O(2^n)$	指數時間	每增加一個輸入，運算量呈指數倍增長	遞迴生成子集、暴力解法

在不同輸入規模 (n) 下，各複雜度的運算次數大致趨勢如下：

輸入大小 (n)	1	10	100	1,000
$O(1)$	1	1	1	1
$O(\log n)$	0	~3	~7	~10
$O(n)$	1	10	100	1,000
$O(n \log n)$	0	~33	~664	~9,966
$O(n^2)$	1	100	10,000	1,000,000
$O(2^n)$	2	1,024	~$10^{30}$	~$10^{301}$

從上面可以觀察到，不同時間複雜度對輸入規模的敏感程度差異很大。 $O(1)$ 的演算法幾乎不受輸入大小影響，執行時間保持穩定；$ O(\log n)$ 的增長非常緩慢，即使輸入增加許多，額外成本仍相對低； $O(n)$ 與 $O(n \log n)$ 在中大型輸入下的差異逐漸顯現，後者雖然比前者稍慢，但仍屬高效演算法；而 $O(n^2)$ 則增長非常快速，對大規模資料而言，執行效率會明顯下降，容易成為性能瓶頸。

常見函式的時間複雜度，2026年1月1日取自維基百科。

Python 範例

以程式語言來說，則各複雜度可以簡單以範例表示如下：

$O(1)$

常數時間演算法的執行步數不隨輸入大小而改變。無論陣列長度為 10 還是 10,000 ，這個函數都只需一次訪問操作。

1
2
3
# O(1)
def get_first_element(arr):
    return arr[0]

$O(\log n)$

對數時間演算法每次將問題規模減半，迅速逼近解答，適合應用於分治策略。對長度為 $n$ 的陣列，最多執行 $\log_2(n)$ 次比較。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
# O(log n)
def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

$O(n)$

線性時間演算法需要遍歷輸入資料一次，執行步數與輸入大小成正比。對長度為 $n$ 的陣列，需要執行 $n$ 次加法操作。

1
2
3
4
5
6
# O(n)
def sum_list(arr):
    total = 0
    for x in arr:
        total += x
    return total

$O(n \log n)$

線性對數時間演算法通常出現在高效排序或分治策略中。對長度為 $n$ 的資料，演算法會遞迴分割資料，再合併結果，因此總運算量約為 $n \times \log_2(n)$。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
# O(n log n)
def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result.extend(left[i:])
    result.extend(right[j:])
    return result

$O(n^2)$

平方時間演算法通常包含雙層迴圈，運算量隨輸入平方增長。對長度為 $n$ 的陣列，總共需要執行 $n \times n$ 次操作

1
2
3
4
5
6
# O(n^2)
def print_pairs(arr):
    n = len(arr)
    for i in range(n):
        for j in range(n):
            print(arr[i], arr[j])

$O(2^n)$

指數時間演算法的運算量隨輸入呈指數增長。即使 $n$ 較小，也可能導致計算量快速膨脹，常見於暴力解法或組合問題。

1
2
3
4
5
6
7
# O(2^n)
def generate_subsets(arr):
    if not arr:
        return [[]]
    first = arr[0]
    rest_subsets = generate_subsets(arr[1:])
    return rest_subsets + [[first] + subset for subset in rest_subsets]

結語

時間複雜度是理解與設計演算法的核心概念。透過分析演算法在不同輸入規模下的增長行為，我們能有效評估其效率，並在性能與資源之間做出合理取捨。掌握時間複雜度不僅有助於選擇適合的演算法，還能指導我們進行程式優化、系統設計，以及面對大規模資料時的策略規劃。

參考資料

時間複雜度。（2025年11月18日）。維基百科，自由的百科全書。2026年1月1日參考自 https://zh.wikipedia.org/wiki/时间复杂度
大O符號。（2025年9月18日）。維基百科，自由的百科全書。2026年1月1日參考自 https://zh.wikipedia.org/wiki/大O符号
Sharon Peng。（2021年4月29日）。時間複雜度 — 漸進函數。Medium。2026年1月1日參考自 https://mycollegenotebook.medium.com/時間複雜度-漸進函數-397ca19cdc4c
胡程維。（2025年9月18日）。初學者學演算法｜從時間複雜度認識常見演算法。Medium。2026年1月1日參考自 https://medium.com/appworks-school/初學者學演算法-從時間複雜度認識常見演算法-一-b46fece65ba5

目錄