矩阵乘法算法时间复杂度

Question

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

Answer 1

使用线性代数,存在比天真O(n ³)实现更好复杂性的算法.Solvay Strassen算法通过将每个2x2子矩阵所需的乘法次数从8减少到7 来实现O(n ^2.807)的复杂度.

最快的已知矩阵乘法算法是Coppersmith-Winograd算法,其复杂度为O(n ^2.3737).除非矩阵很大,否则这些算法不会导致计算时间的巨大差异.实际上,使用并行算法进行矩阵乘法更容易,更快捷.

根据[维基百科](https://en.wikipedia.org/wiki/Coppersmith%E2%80%93Winograd_algorithm),从2014年开始有一个矩阵乘法算法达到O(n ^ 2.3729),而Coppersmith-Winograd算法是最快到2010年. (4认同)

Answer 2

天真的算法,就像你在注释中所指出的那样,你得到的是O(n ^ 3).

确实存在可以减少这种情况的算法,但是您不太可能找到O(n ^ 2)实现.我认为最有效实施的问题仍然存在.

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

请@downhand引用？我以前没有遇到过这个结果。我想阅读证明。 (4认同)
事实证明,O(n ^ 2)是不可能实现的. (3认同)
@downhand 我意识到这篇文章是近一年前的，但我很想看到一个证明。 (2认同)
我能找到的最接近的是 https://arxiv.org/abs/1204.1111 的介绍 (2认同)
@ArunJoshla `n` 这里是要相乘的（方形）矩阵的大小。每个矩阵的大小为`(n,n)`。需要注意的是，严格来说，您不能比 O(n^2) 做得更好，因为您至少必须读取两个矩阵中的每个数字才能将它们相乘。 (2认同)

Answer 3

将m×n矩阵乘以n-by-p矩阵的标准方法具有复杂度O(mnp).如果所有这些对你来说都是"n",那就是O(n ^ 3),而不是O(n ^ 2).编辑:在一般情况下它不会是O(n ^ 2).但是对于特定类型的矩阵,有更快的算法 - 如果你了解更多,你可能会做得更好.