跳轉到

04.3 演算法複雜度初探：離散數學與計算的可操作性#

從「能解」到「多快能解」#

前三節我們回答「有多少？」；本章問「找到答案要多長時間？」。這個轉向的歷史節點是：

  • 1936 年，圖靈：定義了「可計算」，但兩個都可計算的問題，實用上可能天差地遠。
  • 1965 年，Cobham 與 Edmonds：提出「多項式時間 vs 指數時間」的劃分，Edmonds 並首次呼籲研究「好的演算法」（如他的最小成本擴充路徑解最大流）。
  • 1971 年，Cook 的 NP-完全性定理：把「多項式 vs 指數」升級為數學上精確的未解問題 P vs NP——Clay 研究所懸賞百萬美元。

這一章把前幾章的計數成果（ \(n!\) 、 \(2^n\) 、Fibonacci 的 \(\varphi^n\) 、二項式係數）全部兌現成複雜度語言。

漸近記號#

定義#

設 \(f, g\) 為非負函數：

  • \(f = O(g)\) ：存在 \(c, n_0\) ，使 \(n \ge n_0\) 時 \(f(n) \le c\,g(n)\) （上界）。
  • \(f = \Omega(g)\) ： \(g = O(f)\) （下界）。
  • \(f = \Theta(g)\) ：同時成立（緊界）。

注意：大 \(O\) 論的是極限趨勢，常數因子與小規模行為都被抹去；它回答的是「問題規模放大時，代價怎麼長」。

增長賽跑（用 03 章的成果）#

由 Stirling 公式 \(n! \sim \sqrt{2\pi n}(n/e)^n\) ，得到經典排序（由慢到快）：

\[1 \ll \log n \ll n \ll n \log n \ll n^2 \ll 2^n \ll n! \ll n^n\]
import math

for n in (10, 20, 30, 50):
    print(f"n={n}: log2n={math.log2(n):6.1f}  n²={n**2:7d}  "
          f"2^n={2**n:.1e}  n!={math.factorial(n):.1e}")
# n=50: n² = 2.5e3，2^n = 1.1e15，n! = 3.0e64
# n! 已達可觀測宇宙原子數（約 1e80）的量級

工程直覺： \(n^2\) 演算法在 \(n = 10^6\) 時要 \(10^{12}\) 步（分鐘級）， \(2^n\) 在 \(n = 100\) 時需 \(10^{13}\) 倍宇宙年齡——複雜度階之差，不是快慢之差，而是可行與不可行之差。這就是密碼學（128 位金鑰 \(= 2^{128}\) 空間）能站穩腳跟的數學根據，也是 03.1 節乘法法則的回響。

分治與 Master 定理#

合併排序的分析#

合併排序把長 \(n\) 陣列對半分、遞迴排序、線性合併：

\[W(n) = 2\,W(n/2) + n - 1, \qquad W(1) = 0.\]

展開法（延續 04.1）：第 \(i\) 層有 \(2^i\) 個子問題、各長 \(n/2^i\) 、每個合併代價 \(\Theta(n/2^i)\) ，該層總計 \(\Theta(n)\) ；共 \(\log_2 n\) 層，故

\[W(n) = \Theta(n \log n).\]

定理（Master 定理，簡式）#

設 \(T(n) = a\,T(n/b) + \Theta(n^d)\) ， \(a \ge 1, b > 1\) ，則

\[T(n) = \begin{cases}\Theta(n^{\log_b a}) & d < \log_b a\\ \Theta(n^d \log n) & d = \log_b a\\ \Theta(n^d) & d > \log_b a.\end{cases}\]

證明梗概（展開樹 + 幾何級數）：展開樹共 \(a^{\log_b n} = n^{\log_b a}\) 個葉（每葉代價 \(\Theta(1)\) ）。第 \(i\) 層總代價為 \(\Theta(n^d)\,(a/b^d)^i\) ，是公比 \(r = a/b^d\) 的幾何級數： - \(r < 1\) （ \(d > \log_b a\) ）：級數由頂層主導， \(T = \Theta(n^d)\) ； - \(r = 1\) ：各層等額 \(\Theta(n^d)\) ，乘層數 \(\log_b n\) ； - \(r > 1\) （ \(d < \log_b a\) ）：由底層主導， \(T = \Theta(n^{\log_b a})\) 。 \(\blacksquare\)

檢驗：合併排序 \(a=2, b=2, d=1\) ， \(\log_b a = 1 = d\) ，得 \(\Theta(n \log n)\) 。二元搜尋 \(a=1, b=2, d=0\) ，得 \(\Theta(\log n)\) 。Karatsuba 乘法（1960，把 \(n\) 位乘法從 \(n^2\) 降到 \(n^{\log_2 3} \approx n^{1.585}\) ，而掀起演算法學革命） \(a=3, b=2, d=1\) ，得 \(\Theta(n^{1.585})\) 。

演算法策略與其複雜度譜系#

策略 代表問題 複雜度 註記
窮舉 漢諾塔模擬、TSP 暴力 \(O(2^n)\) / \(O(n!)\) 03 章的計數告訴我們窮舉空間多大
分治 合併排序、Karatsuba \(O(n \log n)\) 、 \(n^{1.585}\) Master 定理
貪婪 最小生成樹 \(O(E \log V)\) 需要擬陣理論證明正確性
動態規劃 背包、編輯距離 \(O(nW)\) 、 \(O(n^2)\) 記憶化 04.1 的 Fibonacci
隨機化 快排平均 \(O(n \log n)\) 機率母函數（04.2）
遞迴搜尋 飽和回溯 指數級 Hamiltonian 路徑至今無多項式演算法

例（動態規劃 vs 窮舉）：0-1 背包窮舉 \(2^n\) ；DP 用「前 \(i\) 物、容量 \(w\) 」狀態表降到 \(O(nW)\) ——犧牲記憶體換時間，遞迴式 \(dp[i][w] = \max(dp[i-1][w],\ dp[i-1][w-w_i] + v_i)\) 正是 04.1「按最後一步分類」的直接翻譯。

例（快排平均複雜度，機率母函數的用武之地）：隨機基準點下，期望比較次數滿足

\[E_n = n - 1 + \frac{2}{n}\sum_{k=0}^{n-1} E_k \implies E_n \sim 2n \ln n.\]

（兩邊同乘 \(n\) 後相鄰相消，是 04.1 遠迴技巧與 04.2 生成函數的合奏。）快排最壞 \(O(n^2)\) 但平均 \(O(n \log n)\) 且常數極小——「平均 vs 最壞」的區分，正是離散機率進入演算法學的原因。

P 與 NP：可操作性的極限#

定義（非形式）#

  • P：可在多項式時間求解的判定問題。
  • NP：解的長度多項式，且可多項式時間驗證。

顯然 \(\text{P} \subseteq \text{NP}\) ；是否相等是本世紀最重要的公開問題。

兩個對照組#

  1. Hamiltonian 路徑問題（1857 年 Hamilton 的二十面體遊戲、1859 年 Kirkman 的學校女生問題同源）：給定圖，是否存在經過每頂點恰一次的路徑？驗證一條給定路徑只要 \(O(n)\) （NP 內），但至今沒有已知的多項式演算法。對照組 Euler 路徑（1736，七橋問題）有一行判準：「奇度頂點為 0 或 2」， \(O(n)\) 判定——Euler 容易、Hamilton 難，是 P vs NP 鴻溝的教科書縮影。
  2. TSP：窮舉 \((n-1)!/2\) 條路線——03.2 的排列計數直接量化了絕望程度。Held–Karp 動態規劃（1962）用子集 DP 把 \(O(n!)\) 壓到 \(O(n^2 2^n)\) ，六十年來無人再進一步——組合爆炸可以被馴服，但未必能被消除。

Cook–Levin 定理（1971）：SAT 是 NP-完全的——NP 中任何問題都能多項式歸約到它。此後 Karp（1972）用 21 個歸約把背包、分拆、團、著色等一網打盡。若任何一個 NP-完全問題找到多項式演算法，則 \(\text{P} = \text{NP}\) ，整個 NP 一次全解——歸約把千百個難題捆成一個。

為何本課程要談它：因為「這問題是 NP-完全」本身就是用計數與歸約證明出來的結論；知道邊界在哪，工程師才不會浪費半年尋找不存在的快演算法，而改投精確指數演算法、近似演算法或啟發式。

from itertools import permutations

# Hamiltonian：n=9 時窮舉 8!/2 = 20160 條路線尚可；n=15 即 4.4e10，絕望
def has_hamiltonian_brute(adj, n):
    for perm in permutations(range(1, n), n-1):
        path = (0,) + perm
        if all(adj[path[i]][path[i+1]] for i in range(n-1)):
            return True
    return False

import itertools
def has_hamiltonian_dp(adj, n):
    # Held-Karp：O(n^2 2^n) 子集 DP，n=20 也可行（約 4 億狀態）
    dp = {(1 << v, v): adj[0][v] for v in range(1, n) if adj[0][v]}
    for size in range(2, n):
        new = {}
        for (S, u), w in dp.items():
            if bin(S).count("1") != size - 1: continue
            for v in range(1, n):
                if not (S >> v) & 1 and adj[u][v]:
                    key = (S | (1 << v), v)
                    if key not in new or new[key] > w + adj[u][v]:
                        new[key] = w + adj[u][v]
        dp = new if size > 2 else {**dp, **new}
    return bool(dp)

# 小圖驗證兩法一致
adj = [[0,1,1,0],[1,0,1,1],[1,1,0,1],[0,1,1,0]]
print(has_hamiltonian_brute(adj, 4), has_hamiltonian_dp(adj, 4))  # True True

章末小結#

  • 大 \(O\) / \(\Theta\) / \(\Omega\) 把「多快」形式化；Stirling 與 03 章的計數給出增長階的真實尺規。
  • Master 定理以展開樹與幾何級數一分鐘解掉所有 \(T(n) = aT(n/b) + n^d\) 。
  • 策略光譜：窮舉 → 分治 → 貪婪/DP → 隨機化；DP 是「遞迴 + 記憶化」對 04.1 的直接兌現。
  • Euler 容易、Hamilton 難、TSP 絕望而可馴——P vs NP 是組合爆炸的極限定律。
  • 計數告訴我們問題空間多大；複雜度告訴我們探索空間多貴。兩者合起來，才是「可操作性」的完整圖像。

下一步#

本冊自 03 章的加乘法則出發，經排列組合、容斥與 Pólya、遞迴、生成函數，至此收束於複雜度。下一冊「圖論」將展開另一條主線：從 Euler 的七橋、Kirkman 的學校女生問題、Hamilton 的二十面體，到電話號碼與 Steiner 三元組的網路設計、Ramsey 理論與 EKR 定理——你會發現：本冊的每一件計數工具，在圖的世界裡都有一個新的戰場。