关于Intel-MKL等厂商优化的BLAS Level 2/3函数时间复杂度的咨询

核心结论 #

BLAS Level 2（矩阵-向量乘法dgemv）的O(n²)、Level 3（矩阵-矩阵乘法dgemm）的O(n³)时间复杂度结论完全适用于Intel-MKL、AMD-BLIS、Cray-Libsci这类厂商优化库，SIMD及其他硬件优化仅会降低大O表示法中的前置常数因子，不会改变复杂度的渐近量级。

具体解释 #

• 大O表示法的本质：大O描述的是算法随输入规模增长的渐近趋势，由算法必须执行的基本操作次数的最高量级决定。对于dgemv，无论怎么优化，都需要遍历n×n矩阵的每一个元素并和向量元素做乘加，总操作次数是n²量级；dgemm则需要完成n³次乘加操作，这个核心的操作量级不会因硬件优化改变。
• 厂商优化的作用边界：Intel-MKL、BLIS这类库的优化（包括SIMD指令集加速、循环分块适配缓存、多核并行调度、小尺寸内核微调等），都是在提升执行效率——比如SIMD一次能并行处理4/8/16个浮点数据，把原本需要多次迭代的操作合并，直接降低了完成n²/n³次操作所需的实际时间，但并没有减少操作的量级。这些优化全部作用于大O表示法中的前置常数，而非改变n的幂次。
• 小尺寸内核的特殊性：针对小矩阵的内核微调，只是让小n场景下的常数因子更优（比如避免缓存失效、减少分支开销），但当输入规模n趋近于无穷大时，渐近复杂度依然由n的最高次项主导，小尺寸优化不会动摇这个核心结论。

内容的提问来源于stack exchange，提问作者velenos14