浮点运算计数与复杂度

一次 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 被工程化以弥合的那道鸿沟。