浮點運算計數與複雜度

一次 flop 就是一次浮點運算——一次加、減、乘或除。計數 flop 是估計一個演算法做多少工作、以及該工作如何隨矩陣增大而擴展的最簡單方法。它是數值分析者的首輪成本模型：不是精確的牆鐘時間，而是一個乾淨的首階估計，告訴你當一個演算法已經做完時，哪個還在執行。

每位從業者都熟記的經典計數：稠密 LU 分解（高斯消元）約需 (2/3) n^3 flop；Cholesky 利用對稱性，只需其一半，即 (1/3) n^3；基於 Householder 的 QR 約需 (4/3) n^3；而 SVD 或完整特徵分解需一個不大的常數乘以 n^3。用已有的分解求解只需 O(n^2)。矩陣-矩陣乘法是 2 n^3；矩陣-向量乘法是 2 n^2。

這些計數之所以重要，在於擴展性。一個 O(n^3) 的演算法，輸入翻倍就做八倍的工作；規模增至三倍就慢二十七倍。所以 O(n^2) 與 O(n^3) 之間的差別絕非紙上談兵——它決定了 n = 100000 是一次喝咖啡的工夫還是根本不可行。這正是為什麼每步 O(nnz) 的迭代法在 O(n^3) 不可想象的大規模上占主導。

一個關鍵告誡：flop 計數不是執行時間。在真實硬體上，性能往往受記憶體流量而非算術所限——在快取與主存間搬運資料的代價可能遠超 flop 本身。兩個 flop 計數相同的演算法，因其記憶體存取對快取的友好程度不同，速度可相差十倍。這恰是分塊 BLAS 與 LAPACK 被工程化以彌合的那道鴻溝。