矩阵乘法算法时间复杂度

我想出了用于矩阵乘法的算法。我在某处读到矩阵乘法的时间复杂度为o（n ^ 2）。但我认为我的算法会得出o（n ^

3）。我不知道如何计算嵌套循环的时间复杂度。所以请纠正我。

for i=1 to n
   for j=1 to n    
     c[i][j]=0
     for k=1 to n
         c[i][j] = c[i][j]+a[i][k]*b[k][j]

天真的算法是O（n ^ 3），这是您在注释中指出的更正后得到的结果。

确实存在某种程度上可以减少这种情况的算法，但是您不太可能找到O（n ^ 2）实现。我认为，最有效实施的问题仍然悬而未决。

有关更多信息，请参见Wikipedia上有关“

矩阵乘法”的文章。