矩阵乘法算法的时间复杂度 [英] matrix multiplication algorithm time complexity

问题描述

我想出了这个算法，矩阵乘法。我曾经读过矩阵乘法为O的时间复杂度（N ^ 2）。 但我认为我的这个算法会给O（N ^ 3）。 我不知道如何计算时间嵌套循环的复杂性。所以，请大家指正。

 对于i = 1到n
   对于j = 1到n
     C [I] [J] = 0
     对于k = 1到n
         C [I] [J] = C [I] [J] + A [1] [K] * B [k]的[J]。
 

解决方案

天真的算法，也就是你有什么，一旦你改正它作为评论指出，为O（n ^ 3）。

确实存在的算法，减少这个有点，但你不可能找到一个为O（n ^ 2）执行。我认为，最有效的执行问题仍然是开放的。

查看矩阵乘法这维基百科的文章以了解更多信息。

I came up with this algorithm for matrix multiplication. I read somewhere that matrix multiplication has a time complexity of o(n^2). But I think my this algorithm will give o(n^3). I don't know how to calculate time complexity of nested loops. So please correct me.

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]

解决方案

The naive algorithm, which is what you've got once you correct it as noted in comments, is O(n^3).

There do exist algorithms that reduce this somewhat, but you're not likely to find an O(n^2) implementation. I believe the question of the most efficient implementation is still open.

See this wikipedia article on Matrix Multiplication for more information.

这篇关于矩阵乘法算法的时间复杂度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！