計算與演算法是什麼（進階）：從「能不能算」到「划不划算」

同樣是「可計算」，為什麼有些問題我們解得動、有些卻只能投降？

入門篇我們達成了一個漂亮的結論：只要一個函數「直覺上能被有效計算」，圖靈機(Turing machine)就算得出來——這是 Church–Turing 論題。但這句話藏著一個讓人不安的縫隙。它只談「能不能算」，完全沒談「要算多久」。停機問題(halting problem)那種「原則上無解」的情況其實是少數；現實中真正折磨工程師與研究者的，是另一類問題：它們明明可計算、明明有演算法，但已知的所有演算法都慢到讓宇宙年齡都不夠用。

想像你要替一家有 30 個分店的物流公司規劃一條最短的送貨路線（這就是著名的旅行推銷員問題，Travelling Salesman Problem, TSP）。把所有路線一條條試過去？$30!$ 種排列大約是 $2.65 \times 10^{32}$，即使每秒檢查一兆條，也要算上十兆年。但這個問題明明「可計算」——窮舉法就是個合法演算法。問題不在「能不能」，而在「划不划算」。這一篇，我們把鏡頭從可計算性(computability) 推進到計算複雜度(computational complexity)：一個問題就算有解，它到底「有多難」？這個「難」又是如何被精確定義、分類、甚至證明的？

不只是圖靈機：一座由弱到強的計算模型階梯

入門篇把圖靈機當成「計算」的終極標準，但這會給人一種錯覺，以為所有計算裝置都一樣強。其實在圖靈機之下，還存在一整座自動機(automata)階梯，每一層能辨識的問題嚴格多於下一層。理解這座階梯，你才會明白「為什麼正規表示式(regular expression)無法檢查括號是否配對」這種日常工程現象背後的深層原因。

這座階梯（即 Chomsky 階層，Chomsky hierarchy）由弱到強大致是：

關鍵洞見是：記憶體的結構決定了計算能力。有限狀態機沒有外部記憶，所以它「數不清」，無法判斷一串 ((())) 的左右括號是否一樣多——因為這需要記住「目前還欠幾個右括號」，而那個數字可以無限大，超出有限狀態的負荷。加上一個堆疊就升級成下推自動機，便能配對括號。再把堆疊換成可任意讀寫的無限紙帶，就成了圖靈機。

這解釋了一個經典的工程教訓：不要用正規表示式去剖析 HTML 或巢狀結構。因為 HTML 標籤可以無限巢狀，本質上是上下文無關（甚至更複雜）的，而正規表示式對應的有限狀態機在數學上就「沒有能力」處理任意深度的巢狀。這不是技巧不夠，而是計算模型的先天限制。

# 有限狀態機能輕鬆做的：辨識「a 開頭、c 結尾、中間任意個 b」
import re
print(bool(re.fullmatch(r"ab*c", "abbbc")))   # True

# 它「原則上」做不到的：判斷任意深度的括號是否配對
# 下面這個非正規方法之所以可行，是因為 Python 不是正規引擎，
# 我們其實是手動實作了一個下推自動機（用 list 當堆疊）
def balanced(s):
    stack = []
    for ch in s:
        if ch == '(':
            stack.append(ch)
        elif ch == ')':
            if not stack:      # 多了右括號
                return False
            stack.pop()
    return not stack            # 收尾時堆疊須清空

print(balanced("((()))"))       # True
print(balanced("(()"))          # False

把「難度」量化：漸進分析與成長階級

要比較兩個演算法誰快，我們不數實際毫秒（那受硬體、語言、快取影響太大），而是看輸入規模 $n$ 變大時，工作量如何成長。這就是入門篇提過的大 O 記號，但進階一點，我們需要區分一整個家族：

• $O(f(n))$：成長不快於 $f(n)$（上界）。
• $\Omega(f(n))$：成長不慢於 $f(n)$（下界）。
• $\Theta(f(n))$：成長恰好是 $f(n)$ 等級（上下界都吻合）。

說「排序問題的下界是 $\Omega(n \log n)$」與說「合併排序是 $O(n \log n)$」是兩件不同的事：前者是對問題的論斷（任何基於比較的演算法都逃不掉），後者是對某個解的論斷。當兩者吻合，我們說這個演算法是漸進最優(asymptotically optimal) 的。

不同成長階級的差距是壓倒性的。下表假設電腦每秒處理一億次基本操作：

這張表帶出複雜度理論最重要的一條分界線：多項式時間($n^k$，無論 $k$ 多大) vs 指數時間($2^n$)。多項式時間被視為「可行(tractable)」，指數時間被視為「不可行(intractable)」。這不是因為 $n^{100}$ 真的很快，而是因為多項式對輸入規模的成長是「溫和」的，而指數是「災難性」的：輸入加一個元素，多項式時間頂多乘上一個固定倍數，指數時間卻直接翻倍。

動手算一下：為什麼比較排序逃不出 $n \log n$

入門篇直接告訴你「基於比較的排序下界是 $O(n \log n)$」，這裡我們把這個下界證明出來，讓你看見複雜度下界是怎麼來的。

任何只靠「兩兩比較」來排序的演算法，都可以畫成一棵決策樹(decision tree)：每個內部節點是一次比較（「$a_i < a_j$ 嗎？」），兩個分支對應 Yes / No，每片葉子對應一種最終的排列順序。

關鍵推理分三步：

1. $n$ 個相異元素共有 $n!$ 種可能的排列，演算法必須能區分全部，所以這棵樹至少要有 $n!$ 片葉子。
2. 一棵高度為 $h$ 的二元樹，葉子數最多 $2^h$ 片。要裝下 $n!$ 片，必須 $2^h \geq n!$，即 $h \geq \log_2(n!)$。
3. 樹的高度 $h$ 就是最壞情況下的比較次數。用 Stirling 近似 $\log_2(n!) \approx n \log_2 n - n \log_2 e$，得到 $h = \Omega(n \log n)$。

import math

def comparison_lower_bound(n):
    """任何比較排序在最壞情況下至少需要的比較次數"""
    return math.ceil(math.log2(math.factorial(n)))

for n in [8, 16, 100]:
    lb = comparison_lower_bound(n)
    nlogn = n * math.log2(n)
    print(f"n={n:>3}：下界 {lb} 次比較，n·log₂n ≈ {nlogn:.0f}")
# n=  8：下界 16 次比較，n·log₂n ≈ 24
# n= 16：下界 45 次比較，n·log₂n ≈ 64
# n=100：下界 525 次比較，n·log₂n ≈ 664

結論很美：這個下界與任何具體演算法無關，它是「比較」這個操作本身施加的資訊論限制。無論你發明多巧妙的比較排序，都不可能突破它。（這也順帶解釋了為什麼計數排序、基數排序能達到 $O(n)$——它們不靠比較，而是直接利用數值結構，跳出了決策樹模型。）

P、NP 與那個一百萬美元的問題

現在我們能精確描述本文開頭的困境了。複雜度理論把問題（這裡指「是非題」形式的判定問題）依難度分成複雜度類(complexity class)：

• P 類：存在演算法能在多項式時間內求解的問題。例如「這串數字排好序了嗎？」「兩點間有路徑嗎？」這些都是我們真心解得動的問題。
• NP 類：給定一個候選答案，能在多項式時間內驗證它對不對的問題。注意定義裡是「驗證」而非「求解」。TSP 的判定版（「有沒有總長 $\leq k$ 的路線？」）就在 NP：要你找出那條路線很難，但若有人遞給你一條路線，你能很快加總長度檢查。

顯然 $P \subseteq NP$（能快速求解，當然能快速驗證——自己算一遍就好）。但反過來呢？會不會凡是能快速驗證的問題，其實都能快速求解，只是我們還沒找到聰明演算法？ 這就是電腦科學最著名的未解難題：$P \overset{?}{=} NP$，名列 Clay 數學研究所的七大千禧年難題，懸賞一百萬美元。

絕大多數研究者相信 $P \neq NP$（也就是「驗證」確實比「求解」容易），但至今無人能證明。這個問題之所以重量級，是因為它牽動整個現代社會：若 $P = NP$，許多目前安全的密碼系統會在一夜間崩潰（因為破解就變成可快速求解的問題），但同時最佳化、蛋白質摺疊、AI 規劃等難題也會變得輕而易舉。

NP-完全：一把鑰匙開所有鎖

NP 裡有一群特別的問題叫 NP-完全(NP-complete)，它們是 NP 裡「最難的一批」，而且彼此命運相連。理解它要靠入門篇在「不可計算」脈絡下提過、這裡升級使用的工具——歸約(reduction)。

在複雜度語境下，多項式時間歸約的意思是：若我能用多項式時間的「轉換程序」把問題 A 的任一實例改寫成問題 B 的實例，使得「A 的答案為是」當且僅當「B 的答案為是」，那麼 B 至少和 A 一樣難——因為只要能解 B，就能解 A（先轉換，再解 B）。

1971 年 Cook 與 Levin 證明了布林可滿足性問題(SAT)是 NP-完全的，隨後 Karp 證明了 21 個經典問題（包含 TSP、圖著色、背包問題）也都是。它們的驚人性質是：只要任何一個 NP-完全問題被找到多項式時間解法，所有 NP 問題就全部跟著變成 P（因為任何 NP 問題都能歸約到它）。反之，只要能證明其中一個沒有多項式解，$P \neq NP$ 就成立。這群問題像是被一條看不見的繩子綁在一起，同生共死。

# 概念示範：把「圖著色」歸約成 SAT 的精神
# （這裡只展示「轉換 + 用現成 SAT solver 解」的工程意義，不求完整）
#
# 想用 3 種顏色替地圖上色、相鄰區域不同色（一個 NP-完全問題）？
# 不必發明專用演算法——把它「翻譯」成布林邏輯式，
# 丟給高度優化的 SAT solver。這正是歸約在實務上的價值：
# 數十年投入打磨的單一 solver，能解所有歸約到它的問題。
def region_color_clauses(regions, edges, colors=3):
    clauses = []
    # 變數 x[r][c] = True 代表「區域 r 上第 c 色」
    # 條件一：每個區域至少有一色
    for r in regions:
        clauses.append([f"x_{r}_{c}" for c in range(colors)])
    # 條件二：相鄰區域不可同色
    for (a, b) in edges:
        for c in range(colors):
            clauses.append([f"NOT x_{a}_{c}", f"NOT x_{b}_{c}"])
    return clauses

cl = region_color_clauses(["A", "B"], [("A", "B")])
print(f"產生 {len(cl)} 條子句，交給 SAT solver 即可")

實務上遇到 NP-完全問題並非世界末日。工程師會改用近似演算法(approximation algorithm)（求「夠好」而非「最佳」解）、啟發式(heuristic)（如模擬退火、基因演算法）、或參數化演算法（在輸入的某個小參數上做指數、但對主規模 $n$ 仍多項式）。承認「這問題本質上難」，反而是選對策略的起點。

超越單一序列機器：當「計算」走向隨機、平行與量子

入門篇的圖靈機是確定性(deterministic)、循序(sequential) 的。現代計算把這兩個假設都鬆綁了，衍生出更豐富的計算模型，各自改變了我們對「難度」的判斷。

隨機化演算法(randomized algorithm) 允許演算法擲硬幣。聽起來像作弊，但它常能用簡單的手段達到極高效率。例如要驗證一個數是否為質數，確定性方法曾長期昂貴；而 Miller–Rabin 隨機檢驗能以極高機率快速回答，把出錯機率壓到比硬體故障還低。這催生了複雜度類 BPP（有界錯誤的機率多項式時間）——一個務實的「可行」定義。

平行計算(parallel computing) 把工作分給多個處理器同時做。但「人多好辦事」有其極限：Amdahl 定律(Amdahl's law) 指出，若一個程式有比例 $p$ 的部分能平行化、其餘 $(1-p)$ 必須循序執行，那麼用 $N$ 個處理器最多加速

$$ S(N) = \frac{1}{(1-p) + \dfrac{p}{N}} $$

當 $N \to \infty$，加速上限是 $\frac{1}{1-p}$。也就是說，即使只有 5% 的程式無法平行，無論你堆多少核心，最多也只能快 20 倍。這冷酷地提醒我們：平行化不是萬靈丹，瓶頸往往在那無法切開的循序部分。

def amdahl_speedup(p, N):
    """p：可平行化比例；N：處理器數量"""
    return 1 / ((1 - p) + p / N)

for p in [0.50, 0.90, 0.95]:
    inf = 1 / (1 - p)
    print(f"可平行 {p:.0%}：1024 核加速 {amdahl_speedup(p, 1024):.1f}×，"
          f"理論上限 {inf:.0f}×")
# 可平行 50%：1024 核加速 2.0×，理論上限 2×
# 可平行 90%：1024 核加速 9.9×，理論上限 10×
# 可平行 95%：1024 核加速 19.6×，理論上限 20×

量子計算(quantum computing) 則更根本地改寫規則。它利用量子位元(qubit)的疊加與糾纏，對某些特定問題提供超多項式的加速——最著名的是 Shor 演算法能在多項式時間分解大整數，直接威脅 RSA 加密。但要澄清一個常見迷思：量子電腦並非「什麼都更快」，也不能解圖靈機不可計算的問題。它在可計算性上與古典電腦等價（不違反 Church–Turing 論題），只是對少數結構特殊的問題（因數分解、非結構化搜尋）改變了複雜度。對絕大多數日常計算，它沒有優勢。

重點回顧

• 可計算性問「能不能算」，複雜度問「要算多久」；許多問題可計算卻不可行(intractable)，TSP 的窮舉就是典型——指數時間讓宇宙年齡都不夠用。
• 計算模型構成一座由弱到強的階梯（有限狀態機 → 下推自動機 → 圖靈機），記憶體結構決定能力上限；這正是「正規表示式無法剖析巢狀結構」的數學根源。
• 複雜度的核心分界是多項式時間（可行）vs 指數時間（不可行）；比較排序的 $\Omega(n \log n)$ 下界可由決策樹的資訊論論證嚴格證明，與任何具體演算法無關。
• P 是可快速求解、NP 是可快速驗證；$P \overset{?}{=} NP$ 是懸賞百萬美元的未解難題，NP-完全問題透過多項式歸約彼此綁定、同生共死。
• 隨機化、平行（受 Amdahl 定律約束）、量子計算各自改寫了「難度」的判斷，但都不超越圖靈機的可計算邊界——它們改變效率，而非能力。

深入探討（研究所視角）

時間—空間階層定理：難度是「真實存在」的階梯

我們一直假設「$n^2$ 真的比 $n$ 難、指數真的比多項式難」，但這需要證明——萬一所有複雜度其實偷偷塌縮成同一類呢？時間階層定理(time hierarchy theorem) 保證這種塌縮不會發生：對於行為良好（time-constructible）的函數，若 $f(n) \log f(n) = o(g(n))$，則 $\mathrm{DTIME}(f(n)) \subsetneq \mathrm{DTIME}(g(n))$——也就是說，多給足夠多的時間，確實能解開更多問題。其證明核心是一個精巧的對角化(diagonalization)論證：構造一台機器 $D$，模擬所有「只用 $f(n)$ 時間」的機器並刻意「唱反調」，使 $D$ 的行為無法被任何快速機器複製，從而證明 $D$ 解的問題落在 $g$ 層卻不在 $f$ 層。這與圖靈證明停機問題、Cantor 證明實數不可數同出一脈——對角化是計算理論反覆出現的核心武器。空間方面有平行的空間階層定理。這些定理是複雜度世界「有真實層次」的地基，沒有它們，整套 P/NP 的討論會失去意義。

攤銷分析：當「最壞情況」具有誤導性

大 O 的最壞情況分析有時過度悲觀。考慮 Python 的 list.append：list 容量滿了就要重新配置更大的陣列並複製全部元素，這一次操作是 $O(n)$。若天真地按最壞情況推論，做 $n$ 次 append 就是 $O(n^2)$。但實務上完全不是——因為昂貴的擴容很罕見。攤銷分析(amortized analysis) 處理的正是這種「總成本攤到每次操作」的平均行為。以 CPython 採用的成長策略（容量約以固定比例放大）為例，用會計法(accounting method) 或位能法(potential method) 可證明：$n$ 次 append 的總成本是 $O(n)$，故每次 append 的攤銷成本是 $O(1)$。

# 觀察 list 擴容的攤銷行為：絕大多數 append 是廉價的
import sys

prev = -1
reallocations = 0
data = []
for i in range(1000):
    data.append(i)
    cap = (sys.getsizeof(data) - sys.getsizeof([])) // 8  # 估算容量
    if cap != prev:
        reallocations += 1
        prev = cap
print(f"1000 次 append 只觸發約 {reallocations} 次擴容")
# 昂貴操作的次數隨總量呈對數級，故每次平均仍是 O(1)

攤銷分析是區分「單次最壞」與「序列平均」的關鍵工具，在動態陣列、splay tree、union-find 等資料結構的分析中不可或缺——union-find 配合路徑壓縮與按秩合併，每次操作攤銷成本是反 Ackermann 函數 $\alpha(n)$，對任何實際 $n$ 都小於 5，幾近常數。

計算模型的穩健性：為什麼我們敢只談「多項式」

最後一個深刻問題：我們把「多項式時間」當成跨模型的「可行」標準，但不同機器（單帶圖靈機、多帶圖靈機、RAM 模型、你的筆電）速度明明不同，憑什麼用同一個門檻？答案是強 Church–Turing 論題(strong/extended Church–Turing thesis)：所有「合理的」確定性計算模型，彼此之間最多差一個多項式因子。多帶圖靈機模擬單帶最多平方級開銷，RAM 模型與圖靈機互模擬也是多項式級。因此「多項式 vs 指數」這條分界對模型選擇免疫——P 這個類在所有古典模型上都是同一個 P。這正是複雜度理論敢於抽象掉硬體細節、只談成長階級的底氣。值得注意的是，量子計算對這條強論題提出了挑戰（BQP 可能嚴格大於 P），這也是量子計算在理論上引人入勝的原因之一：它撼動的不是「能算什麼」，而是「能在多項式時間內算什麼」這道更精細的防線。