1.1 什麼是計算複雜度#

概念說明#

當我們寫出一個演算法，最自然的問題是：「它跑得快嗎？」要回答這個問題，我們不能只靠秒表計時，因為實際的執行時間受到電腦速度、程式語言、編譯器最佳化等太多因素影響。計算複雜度（computational complexity）提供了一個抽象且客觀的度量方式：統計演算法執行基本運算的次數，如何隨著輸入大小的成長而變化。

輸入大小通常記作 n，例如陣列的元素個數、圖的頂點數、數字的位元數。演算法的執行步驟數被表示為 n 的函數，稱為時間複雜度，記作 T(n)。我們通常用「大 O 記號」（Big-O notation）來描述成長率的上界，只保留最高階項並忽略常數係數。例如 T(n) = 3n² + 5n + 7 會記作 O(n²)。

為什麼可以忽略常數與低階項？因為複雜度分析關心的是「規模變大之後」的行為。當 n 足夠大時，n² 遠大於 5n，3 倍的常數差距也遠不及演算法階數的差異。一個 O(n log n) 的演算法，在 n 足夠大時一定會勝過 O(n²) 的演算法，無論後者的程式寫得多麼精巧。

常見的複雜度階層由快到慢排列如下：

表格中最後兩行值得特別注意：指數與階乘成長的演算法，在輸入稍微變大時就會完全失去實用性。假設一台電腦每秒能執行 10⁹ 次運算，一個 2ⁿ 步的演算法在 n = 60 時需要超過 300 年；而 n = 100 時，所需時間已超過宇宙年齡。這正是 NP 問題困難的根源——許多看似簡單的問題，已知最好的演算法都是指數時間。

演算法步驟：如何做複雜度分析#

1. 找出輸入大小的度量 n（元素個數、位元數、頂點數等）。
2. 逐一檢視程式中的每個迴圈與遞迴結構。
3. 巢狀迴圈：外層執行 f(n) 次、內層執行 g(n) 次，總工作量為 f(n) × g(n)。
4. 順序執行的兩段程式碼：總工作量為兩者相加，取較大者作為整體複雜度。
5. 遞迴演算法：寫出遞迴關係式（如 T(n) = 2T(n/2) + O(n)），再用主定理（Master Theorem）或展開法求解。
6. 最後以大 O 記號表達，保留最高階項、去掉常數。

Python 程式碼範例#

下面的程式碼比較了兩種「找出一陣列中是否存在兩數之和等於目標值」的方法：暴力法是 O(n²)，排序加雙指標是 O(n log n)。我們用計數器實測兩者的基本運算次數。

import random
import bisect

def two_sum_brute(nums, target):
    """暴力法：檢查所有配對，O(n^2)"""
    count = 0
    n = len(nums)
    for i in range(n):
        for j in range(i + 1, n):
            count += 1
            if nums[i] + nums[j] == target:
                return True, count
    return False, count

def two_sum_sorted(nums, target):
    """排序＋二分搜尋：O(n log n)"""
    count = 0
    arr = sorted(nums)          # O(n log n)
    for i in range(len(arr)):
        count += 1
        complement = target - arr[i]
        pos = bisect.bisect_left(arr, complement, i + 1)
        count += max(1, (len(arr) - i - 1)).bit_length()
        if pos < len(arr) and arr[pos] == complement:
            return True, count
    return False, count

# 實驗：觀察運算次數隨 n 的成長
print(f"{'n':>8} {'暴力法次數':>14} {'排序法次數':>14}")
for n in [100, 200, 400, 800]:
    nums = random.sample(range(1, 10**6), n)
    _, c1 = two_sum_brute(nums, -1)      # 不存在答案的悲觀情況
    _, c2 = two_sum_sorted(nums, -1)
    print(f"{n:>8} {c1:>14} {c2:>14}")

執行後可以觀察到：n 每次加倍，暴力法的運算次數大約變成四倍（n² 的特徵），而排序法只大約變成兩倍多一點（n log n 的特徵）。這種「倍增實驗」是實務上驗證複雜度階數的簡便方法。

複雜度分析#

• two_sum_brute：兩層巢狀迴圈，最壞情況執行 n(n−1)/2 次比較，時間複雜度 O(n²)，空間複雜度 O(1)。
• two_sum_sorted：排序需要 O(n log n)，之後每個元素做一次二分搜尋 O(log n)，總共 O(n log n)，空間複雜度 O(n)（排序副本）。
• 本範例說明一個重要觀念：同一個問題可能有多種演算法，複雜度差異可能巨大。選對演算法往往比買更好的硬體更有效——這句話在面對 NP-hard 問題時將變成一本書的主題。

練習#

1. 請分析下列程式碼的時間複雜度，並說明理由：

   i = 1
   while i < n:
       print(i)
       i = i * 2
   

   （提示：i 每次乘 2，執行次數為 log₂n。）
2. 試修改 two_sum_sorted，改用雜湊表（dict/set）達到平均 O(n) 的時間複雜度，並與暴力法進行倍增實驗比較運算次數。
3. 假設某演算法在輸入大小 n = 1000 時需要 1 秒，若其複雜度為 O(n³)，估算 n = 10⁶ 時需要多久（以天為單位）。若複雜度為 O(2ⁿ) 呢？請用 Python 計算並討論其含義。