附錄 B 重要演算法時間空間複雜度速查表
本附錄彙整書中出現的主要演算法之時間與空間複雜度。複雜度分析始於高斯時代對運算次數的計數，但現代意義上的漸進記號要到 Landau（1909、1924）才被系統化；1970 年代 Knuth 將其定為演算法分析的標準語言。以下表格中，\(n\) 為主要規模參數，每行附帶一句關鍵假設，因為同一演算法在不同假設下（稠密或稀疏、是否 pivot、收斂率類型）複雜度可能相差甚遠。
B.1 線性代數與數值線性代數
| 問題 / 演算法 | 時間複雜度 | 空間複雜度 | 關鍵假設 |
| 稠密矩陣—矩陣乘法 | \(O(n^3)\) | \(O(n^2)\) | 稠密、一般矩陣、經典三重迴圈 |
| Strassen 演算法 | \(O(n^{\log_2 7}) \approx O(n^{2.81})\) | \(O(n^{\log_2 7})\) | \(n\) 為 2 的冪（需 padding），數值穩定性略遜經典法 |
| 理論最好界 | \(O(n^{\omega})\)，\(\omega \lesssim 2.37\) | — | 目前最好（如 Alman–Duan–Vassilevska Williams 等的 \(2.371552\)）僅為理論結果，常數巨大，實務不用 |
| 稀疏矩陣—向量乘 | \(O(\mathrm{nnz})\) | \(O(\mathrm{nnz})\) | 以 CSR/CSC 儲存，\(\mathrm{nnz}\) 為非零元素數 |
| LU 分解（含 partial pivoting） | \(\tfrac{2}{3}n^3 + O(n^2)\) | \(O(n^2)\) | 稠密、需 pivoting 保穩定性；稀疏時受 fill-in 主導 |
| Cholesky 分解 | \(\tfrac{1}{3}n^3 + O(n^2)\) | \(O(n^2)\) | 對稱正定，不需 pivoting，成本約為 LU 一半 |
| QR 分解（Householder） | \(2n^3 + O(n^2)\)（矩陣同形 \(m=n\)） | \(O(n^2)\) | 一般稠密矩陣；\(m \times n\) 時為 \(O(mn^2)\) |
| 三對角 LU（Thomas 演算法） | \(O(n)\) | \(O(n)\) | 帶狀結構（頻寬固定），不需選主元 |
| SVD（Golub–Kahan） | \(O(mn^2)\)，\(m \ge n\) | \(O(mn)\) | 一般稠密矩陣，需迭代求特徵值；計算所有奇異向量時為主導成本 |
| 對稱特徵值分解 | \(O(n^3)\) | \(O(n^2)\) | 對稱矩陣；QR 演算法或 divide-and-conquer |
| 稀疏直接法（Cholesky） | 依填入而定，最壞 \(O(n^3)\) | 受 fill-in 主導 | 依好排序（如巢狀剖分、AMD）可近 \(O(n^{1.5})\) 等於二維網格問題 |
| 共軛梯度法（CG） | 每步 \(O(\mathrm{nnz})\) | \(O(\mathrm{nnz})\) | 對稱正定；誤差 \(\|e_k\|_A \le 2(\tfrac{\sqrt{\kappa}-1}{\sqrt{\kappa}+1})^k \|e_0\|_A\)，理想平坦譜時至多 \(n\) 步收斂 |
| GMRES | 每步 \(O(\mathrm{nnz} + k n)\) | Arnoldi 基底 \(O(kn)\) | 非對稱矩陣；第 \(k\) 步需儲存全部基底，故需重啟 |
B.2 傅立葉與訊號處理
| 演算法 | 時間複雜度 | 空間複雜度 | 關鍵假設 |
| 直接 DFT | \(O(n^2)\) | \(O(n)\) | 直接計算 \(n\) 個基函數內積 |
| Cooley–Tukey FFT | \(O(n \log n)\) | \(O(n)\) | \(n\) 為 2 的冪（radix-2）；一般混合基仍為 \(O(n\log n)\) |
| 多維 FFT | \(O(N \log N)\)（\(N\) 為總點數） | \(O(N)\) | 各維獨立，逐維做一維 FFT |
B.3 最佳化
| 演算法 | 時間複雜度 | 空間複雜度 | 關鍵假設 |
| 單純形法（simplex，Dantzig 1947） | 指數級最壞情況（Klee–Minty 1972 反例），實務平均 \(O(m n)\) 級 | \(O(mn)\) | 線性規劃 \(m \times n\) 約束；實務上迭代數量約為約束數的線性倍 |
| 內點法（interior point，Karmarkar 1984） | \(O(\sqrt{n} \, L)\) 次迭代，總多項式時間 | \(O(n^2)\) 以上（需解牛頓系統） | 線性規劃；每步需解稀疏牛頓系統，實際迭代數通常 20–50 次、與規模弱相關 |
| 梯度下降（光滑凸） | \(O(\kappa \log(1/\varepsilon))\) 次迭代 | \(O(n)\) | 函數 \(L\)-光滑且 \(\mu\)-強凸，\(\kappa = L/\mu\)；線性收斂率 |
| Nesterov 加速梯度法 | \(O(\sqrt{\kappa} \log(1/\varepsilon))\) 次迭代 | \(O(n)\) | 同上；加速後最佳一階複雜度 |
| 牛頓法 | 每步 \(O(n^3)\)（解 Hessian 系統） | \(O(n^2)\) | 二階光滑、Hessian 非奇異；二次收斂（局部） |
| 擬牛頓法（BFGS） | 每步 \(O(n^2)\) | \(O(n^2)\) | 光滑函數；超線性收斂，不需精確 Hessian |
B.4 隨機方法
| 演算法 | 時間複雜度 | 空間複雜度 | 關鍵假設 |
| MCMC（Metropolis–Hastings，1953/1970） | \(O(K)\) 步，每步 \(O(\text{模型評估})\) | \(O(\text{狀態維度})\) | 目標分佈已知至正規化常數；需混合時間（mixing time）控制，慢混合時 \(K\) 可能極大 |
| 蒙地卡羅積分 | \(O(N)\) 個樣本，誤差 \(O(N^{-1/2})\) | \(O(1)\) | 獨立取樣；收斂率與維度無關（與決定論網格的 \(O(N^{-d/n})\) 相比是優勢） |
B.5 計算幾何
| 演算法 | 時間複雜度 | 空間複雜度 | 關鍵假設 |
| 凸包（二維，Graham scan，1972） | \(O(n \log n)\) | \(O(n)\) | 平面點集；下界 \(\Omega(n \log n)\)（排序歸約） |
| 凸包（三維，增量法） | \(O(n \log n)\) 期望 | \(O(n)\) | 一般位置（no degeneracy） |
| Voronoi 圖（二維） | \(O(n \log n)\) | \(O(n)\) | 平面點集；Voronoi 圖至多 \(3n-6\) 個頂點 |
| Delaunay 三角化 | \(O(n \log n)\) | \(O(n)\) | 與 Voronoi 對偶；空圓性質保證唯一（一般位置下） |
| KD-tree 建樹 | \(O(n \log n)\) | \(O(n)\) | 座標可排序 |
| KD-tree 最近鄰查詢 | 平均 \(O(\log n)\)（低維），最壞 \(O(n)\) | \(O(n)\) | 假設維度 \(d\) 固定且低；\(d\) 大時退化为掃描（維度災難） |
B.6 自動微分
| 模式 | 時間複雜度 | 空間複雜度 | 關鍵假設 |
| 前向模式（forward mode） | \(O(n)\) 倍原函數成本（\(n\) 為輸入維度） | \(O(1)\) 倍原空間 | 一次算一個方向導數；適合 \(m \gg n\)（輸出遠多於輸入） |
| 反向模式（reverse mode） | 常數倍原函數成本（理論上 \(\le 4\) 倍，實務 2–5 倍），可算全梯度 | \(O(\text{原空間}) \times\) 執行長度（需存 tape） | 需記錄所有中間量（tape/checkpointing）；適合 \(n \gg m\)，是反向傳播的數學基礎 |
B.7 使用提醒
- 上表給的是漸進上界；實際效能取決於常數因子、記憶體存取模式與硬體（見第 11.1 節 BLAS 分層的討論）。
- 複雜度對數中的基底不影響 \(O(\cdot)\) 記號，但在比較 FFT 實作（如 radix-2 與 radix-4）時有意義。
- 疊代法的「複雜度」應換算為達到精度 \(\varepsilon\) 所需迭代數 \(\times\) 每步成本，收斂率（linear/quadratic/superlinear）正是這個換算的核心，見附錄 C。