矩阵乘法算法时间复杂度

我想出了这个矩阵乘法算法。我在某处读到矩阵乘法的时间复杂度为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]

来源

2011-12-17 zedai

'b [i] [k]'看起来不对。我怀疑你希望在最后一行的RHS上有'c [i] [j] + a [i] [k] * b [k] [j]'这样的东西。 – 2011-12-17 18:04:32

没有它的正确。这里c [i] [j]是结果矩阵 – zedai 2011-12-17 18:06:14

那么，在这种情况下，你绝对不是在做矩阵乘法！注意，对于给定的'i'，你在'c [i] [j]'中为每个'j'计算相同的结果，所以在你的输出矩阵'c'中，所有的列都是相同的。你需要在最后一行用'b [k] [j]'替换'b [i] [k]'。 – 2011-12-17 18:18:21

天真的算法，这是你一旦你纠正它，如注释中指出的那样，是O（n^3）。

确实存在减少这种情况的算法，但您不太可能找到O（n^2）实现。我认为最有效的实施问题仍然是开放的。

有关更多信息，请参阅此维基百科有关Matrix Multiplication的文章。

来源

2011-12-17 18:34:46

将m乘n矩阵乘以n乘p矩阵的标准方法的复杂度为O（mnp）。如果所有这些对你来说都是“n”，那么它就是O（n^3），而不是O（n^2）。编辑：在一般情况下它不会是O（n^2）。但是对于特定类型的矩阵有更快的算法 - 如果你知道更多，你可能会做得更好。

来源

2011-12-17 18:01:26

这是错误的。一般情况下有加速。 – jwg 2014-06-08 22:35:15

斯特拉森的算法？当然。 OP要求O（n^2），这在一般情况下是不可能的。这正是我所掌握的。 – 2014-06-09 11:38:27

使用线性代数，存在的算法实现比原始O更好的复杂性（n ）。 Solvay Strassen算法通过减少对每个2×2子矩阵所需的乘法的数量从8至7

最快已知矩阵乘法算法是Coppersmith-Winograd算法具有复杂度O（实现了为O（n ^2.807）的复杂性n ^2.3737）。除非矩阵很大，否则这些算法不会导致计算时间的巨大差异。在实践中，使用矩阵乘法的并行算法更容易，更快速。

来源

2011-12-18 06:36:08 viswanathgs

根据[Wikipedia]（https://en.wikipedia.org/wiki/Coppersmith%E2%80%93Winograd_algorithm），2014年有一个矩阵乘法算法实现了O（n^2.3729），而Coppersmith-Winograd算法是最快至2010年。 – Garrett 2014-10-24 05:23:37

-1

在矩阵乘法中有3个for循环，我们正在使用，因为每个for循环的执行需要时间复杂度O(n)。因此，对于三个循环，它变成O(n^3)

来源

2013-01-30 09:28:22 user2024721

矩阵乘法算法时间复杂度

回答

相关问题