有没有任何方法可以将矩阵乘以O（n）复杂度？
我想将两个矩阵相乘，但三重循环具有O（n 3 ）复杂度。 动态规划中是否有任何算法将两个矩阵与O（n）复杂度相乘？
好吧，我们不能得到最好的O（n 2.81 ）
编辑：但有没有任何解决方案，甚至可以将结果近似到一些特定的否。 列和行的矩阵
我的意思是我们得到O（n 2.81 ）中最好的一个复杂的解决方案，但结果却很完美但是如果有任何解决方案甚至近似矩阵的乘法，因为我们有因子近似等公式。
如果有任何你知道它会帮助我
问候。
目前已知的最佳矩阵乘法算法是具有O（n 2.38 ）复杂度的“Coppersmith-Winograd算法” ，但它不用于实际目的。
但是，您总是可以使用具有O（n 2.81 ）复杂度的“Strassen算法” ，但是没有这种已知的算法用于具有O（n）复杂度的矩阵乘法。
在O（n ^ 2）处存在矩阵乘法的理论下界，因为您必须触摸许多存储器位置来进行乘法。 正如其他人所说，有些算法将我们降低到O（n ^ 3）以下，但在实际使用中通常是不切实际的。
如果你需要加快速度，你可能需要查看Cache Oblivious Algorithms，例如加速性能的这一算法（ http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.44.5650 ）通过以缓存内聚方式执行操作，确保数据在需要时位于缓存中。
简答：不
答案很长：如果你有特殊类型的基质（例如对角矩阵），有很多方法。 更好的矩阵乘法算法可以让你减少像O（n 2.4 ）（ http://en.wikipedia.org/wiki/Coppersmith-Winograd_algorithm ）。 我熟悉的主要方法是使用分而治之算法来分解工作负载（而不是我链接的工作负载）。
我希望这有帮助！
如果已知矩阵是对角线的，则可以在O(N)运算中将它们相乘。 但总的来说，你做不到。
矩阵具有O（n 2 ）个元素，并且每个元素必须至少考虑一次用于结果，因此矩阵乘法算法不可能在少于O（n 2 ）个运算中运行。
如果
- 你的矩阵很大
- 他们有很多零
- 你愿意以奇怪的格式存储它们
您可以设计算法，其复杂性仅取决于非零元素的数量。 对于某些问题（例如，有限元方法），这可能是强制性的。
没有！ 我不这么认为。
除非您使用并行处理机器，否则没有办法。 它也有它自己的依赖和限制。
直到现在，它尚未实现。
如果你有n²处理器和共享读存储器架构，你可以在O(n)时间内乘以两个矩阵……但这只是现在的理论。