1.2 多項式時間與有效率演算法#

概念說明#

上一節我們看到各種複雜度階層。電腦科學家在 1960 年代（Cobham 與 Edmonds）提出一個影響深遠的定義：如果一個演算法的執行時間是輸入大小 n 的多項式函數（如 n、n log n、n²、n⁵），我們就稱它在多項式時間（polynomial time）內運作，並視之為「有效率的」演算法。相對地，2ⁿ、n!、nⁿ 這類成長被稱為指數時間，通常被視為「沒有效率的」。

這個分界乍看之下很武斷：O(n¹⁰⁰) 的演算法實務上根本不能用，而 O(n^(1.0001)) 也未必快。但多項式時間作為理論分界有其深刻理由：

封閉性：多項式對加法、乘法、合成皆封閉。把一個多項式時間的演算法呼叫另一個多項式時間演算法，結果仍是多項式時間。這使理論分析穩健，不受實作細節影響。
與計算模型無關：無論用圖靈機、位元運算模型還是合理的真實電腦，多項式時間的判定結果一致（最多差一個多項式倍數），這個性質稱為 robustness。
經驗上的分水嶺：歷史經驗顯示，一個問題一旦找到了多項式時間演算法（即使一開始是 O(n⁶)），往往會持續被改良到實用的程度；而遲遲找不到多項式演算法的問題，多半是真正的難題。

「有效率」與「可行」是兩件事。理論上的有效率指的是成長率的類別，實務上的可行則要看常數、輸入規模與時間預算。本書談 NP 問題時，「多項式 vs 指數」這條線是核心；但在工程實務上（第 7、8 章），我們會看到許多讓指數演算法變得「勉強可用」的技巧。

演算法步驟：判斷一段演算法是否為多項式時間#

確認輸入大小的定義。特別注意：對「數字」而言，輸入大小是它的位元數 log m，而不是數值 m 本身。例如判斷 m 是否為質數，若逐一測試 2 到 √m，複雜度是 O(√m) = O(2^(log m / 2))，其實是指數時間！
分析演算法的迴圈與遞迴，得出以 n 表示的步數上界。
檢查上界是否可被某個多項式 nᵏ 掌控（即上界為 O(nᵏ)）。
若是，則該演算法為多項式時間；否則（如含 2ⁿ、n!）為指數時間。

Python 程式碼範例#

以下用「判斷質數」示範輸入大小定義的陷阱，並實作一個真正的多項式（其實是對數級）演算法——Miller-Rabin 概率測試的簡化版（此處以試除到√n 與線性篩說明）：

import math

def is_prime_trial(m):
    """逐一試除到 sqrt(m)。
    注意：m 是數值，輸入大小是位元數 L = log2(m)，
    所以這其實是 O(2^(L/2)) —— 位元意義下的指數時間！"""
    if m < 2:
        return False
    for d in range(2, math.isqrt(m) + 1):
        if m % d == 0:
            return False
    return True

def is_prime_bitwise_aware(m, witnesses=(2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37)):
    """Miller-Rabin 確定性版本（對 64 位元內整數正確）。
    對位元數 L = log2(m) 而言是 O(L) 輪模冪，每輪 O(L^2)~O(L^3)，
    是位元數的多項式時間 —— 這才是有效率的演算法。"""
    if m < 2:
        return False
    for p in witnesses:
        if m % p == 0:
            return m == p
    d, s = m - 1, 0
    while d % 2 == 0:
        d //= 2
        s += 1

    def check(a):
        x = pow(a, d, m)
        if x in (1, m - 1):
            return True
        for _ in range(s - 1):
            x = x * x % m
            if x == m - 1:
                return True
        return False

    return all(check(a) for a in witnesses)

# 比較：對一個 19 位數測試
big = 2_147_483_647 * 2_147_483_629  # 兩個梅森質數相乘附近的大數
import time
t0 = time.time(); r1 = is_prime_trial(big); t1 = time.time()
t2 = time.time(); r2 = is_prime_bitwise_aware(big); t3 = time.time()
print(f"試除法: {r1}, 耗時 {t1 - t0:.3f} 秒")
print(f"Miller-Rabin: {r2}, 耗時 {t3 - t2:.6f} 秒")

執行後會看到：對十幾位數的輸入，試除法已經要花上數秒甚至分鐘，而 Miller-Rabin 幾乎瞬間完成。原因正是輸入大小應該用位元數衡量——試除法對位元數是指數的，Miller-Rabin 是多項式的。

複雜度分析#

試除法：對數值 m 為 O(√m)；對位元數 L = log₂m 為 O(2^(L/2))，指數時間。
Miller-Rabin：對位元數 L 為 O(k·L³)（k 為見證數個數，此處 k = 12 為常數），多項式時間。
2002 年 Agrawal、Kayal 與 Saxena 的 AKS 演算法證明了質數判定有（不需隨機性的）多項式時間演算法，複雜度 O(L⁶) 等級，是「有效率演算法」定義實際引導研究的著名例子。

練習#

某演算法對數值 n 需要 O(n) 步，n 是一個 64 位元整數。請問它對輸入位元數 L 而言是什麼複雜度？是否屬於多項式時間？
實作函數 factorial_steps(n) 回傳計算 n! 本身值所需的位元運算規模，並說明為什麼「計算 n! 的精確值」嚴格來說不是對 n 的多項式時間（提示：輸出本身有 O(n log n) 個位元）。
請寫一個倍增實驗程式，實測 is_prime_trial 對逐漸加大的隨機質數（如 10 位、12 位、14 位）的耗時，驗證其耗時大約每次加倍輸入位元數就變成 4 倍（因為 2^(L/2) 的特性）。