計算複雜度

計算複雜度是指一個演算法的成本——通常是算術運算次數（flops）或時間，有時是記憶體——如何隨問題變大而增長。它是大 O 符號的另一個意義：工作量 = O(f(n)) 說的是對大的 n，運算次數被某常數乘以 f(n) 所界定，其中 n 衡量問題規模（未知數、資料點、或網格格子的數目）。它是精度-成本-穩定三角形中預算的那一面。

重要的是增長速率，因為它決定一個方法是否能擴展。對 n 個數求和是 O(n)——線性、廉價。快速傅立葉轉換是 O(n log n)——近乎線性，這正是它具革命性的原因。把兩個 n 階矩陣相乘，或用高斯消去法解稠密線性系統，是 O(n^3)——立方，所以 n 加倍，工作量變八倍。O(2^n) 的方法是指數的，超出極小的 n 就無望。對解 A x = b：稠密 LU 求解是 O(n^3)，但同一個答案對三對角系統只花 O(n)，而對稀疏問題，預條件良好的迭代法可接近 O(n)——同一個答案，成本天差地別。

複雜度重要，因為決定可能與否的不只是精度、還有成本：一個在 n = 1000 時還好的 O(n^3) 演算法，在 n = 1,000,000 時變得貴上十億倍。但成本的大 O 與誤差的大 O 共享相同的警告：它是漸近的、隱藏常數（O(n log n) 的方法在小 n 時可能輸給 O(n^2)）、且計的是運算次數而非牆鐘時間。在現代硬體上，低 flop 的方法若搬動大量記憶體仍可能跑得慢——許多真實核心受記憶體限制，受制於快取失誤與資料搬移而非 flop 數，所以複雜度是必要的，卻不是故事的全部。