浮點運算次數

在執行演算法之前，你常想大致知道它要做多少算術，好預測它是一秒就跑完還是要一週。浮點運算次數正是這個估計：演算法所執行的浮點運算（對實數的加、減、乘、除）的個數。一次這樣的運算就是一個 flop。對線性代數而言，它是衡量成本的標準粗估方式。

最重要的是這個次數如何隨問題規模 n 成長，以大 O 記號表示。用 LU 分解解一個稠密的 n×n 系統，分解約需 2 n^3 / 3 次浮點運算，再加上每次前代與回代求解約 n^2 次。對稱正定矩陣的喬列斯基分解只需一半的分解工作，約 n^3 / 3。矩陣-向量乘積 A x 約 2 n^2 次；矩陣-矩陣乘積約 2 n^3 次。當 n 大時立方項主宰一切：n 加倍會讓 LU 分解約慢八倍，因為 2^3 = 8。

計算浮點運算次數告訴你漸近的全貌，讓你比較不同演算法——這正是「分解一次、求解多次」（一次 n^3 分解，之後多次 n^2 求解）遠勝於對每個右端重新消去的原因。但要誠實面對它的限制：在現代硬體上，實際執行時間往往由資料在快取與記憶體間如何移動決定，而非單純的浮點運算次數，所以受記憶體限制的核心可能遠比其浮點運算次數所暗示的慢。這個落差正是為何要有分塊、感知快取的 BLAS 與 LAPACK 程序。