如何衡量多项式运行时间？矩阵乘法算法复杂度分析疑问

核心操作次数统计 #

先看你提供的Java矩阵乘法代码，三层嵌套循环是复杂度的核心：

• 外层i循环执行ra次（ra是矩阵a的行数）
• 中层j循环执行ra * cb次（cb是矩阵b的列数）
• 内层k循环执行ra * cb * ca次（ca是矩阵a的列数，同时也是矩阵b的行数，矩阵乘法要求b的行数等于a的列数）

内层循环里的c[i][j] = c[i][j] + a[i][k] * b[k][j]包含1次乘法、1次加法、2次数组访问、1次赋值，共5次基础操作。再加上三层循环的初始化、条件判断、自增操作，最终总操作数的多项式表达式可以整理为：
8ra·ca·cb + 4ra·cb + 3ra + C
其中C是初始化变量、创建结果数组等固定次数的操作常数。

输入规模n的合理定义 #

你考虑用(ra * ca) + (b.length * cb)作为n，这个思路是把输入矩阵的总元素数作为规模，但有两个关键点需要明确：

1. 矩阵乘法的合法性要求b.length = ca，所以这个n实际是ra·ca + ca·cb = ca(ra + cb)
2. 这种定义方式并不直观，因为矩阵乘法的复杂度本质由矩阵的维度决定，而非总元素数。行业内更常用的定义方式有两种：
   • 以最大维度为n：令n = max(ra, ca, cb)，当矩阵是方阵（ra=ca=cb=n）时，多项式表达式简化为8n³ +4n² +3n +C，大O复杂度为O(n³)——这是矩阵乘法复杂度的标准表述。
   • 以总元素数为n：如果坚持用总元素数作为n，不能直接假设最外层循环次数是n/4，因为这个比例完全取决于ra、ca、cb的维度比例。比如当ra=ca=cb=k时，n=2k²，外层循环次数ra=k=√(n/2)，和n/4没有固定关系。

大O复杂度结论 #

• 若以最大维度n定义输入规模，大O复杂度为O(n³)
• 若以总元素数n定义，复杂度为O(n^(3/2))（当各维度同阶增长时），但这种表述很少被使用，因为无法体现矩阵乘法的维度特性。

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