c++ - 是否有任何方法可以将具有 O(n) 复杂度的矩阵相乘？

Question

我想将两个矩阵相乘，但三重循环的复杂度为 O(n³)。动态规划中是否有任何算法可以将两个复杂度为 O(n) 的矩阵相乘？

好吧，我们不能比 O(n^2.81) 更好

编辑: 但是有没有任何解决方案可以将结果近似到某个特定的数字。矩阵的列和行数

我的意思是我们得到了 O(n^2.81 ) 中最好的一个复杂的解决方案但完美的结果但是如果有任何解决方案即使是矩阵乘法的近似值，因为我们有阶乘近似的公式等等

如果有你知道的，会帮助我的

问候。

Answer 1

目前已知的最佳矩阵乘法算法是 "Coppersmith-Winograd algorithm" 具有 O(n^2.38 ) 复杂性，但不用于实际目的。

但是，您始终可以使用 "Strassen's algorithm" 具有 O(n^2.81 ) 复杂度，但没有这样的已知算法用于具有 O(n) 复杂度的矩阵乘法。