我想将两个矩阵相乘，但三重循环具有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，例如加速性能的这一算法（ ）通过以缓存内聚方式执行操作，确保数据在需要时位于缓存中。
简答：不
答案很长：如果你有特殊类型的基质（例如对角矩阵），有很多方法。 更好的矩阵乘法算法可以让你减少像O（n 2.4 ）（ ）。 我熟悉的主要方法是使用分而治之算法来分解工作负载（而不是我链接的工作负载）。
我希望这有帮助！
如果已知矩阵是对角线的，则可以在O(N)运算中将它们相乘。 但总的来说，你做不到。
矩阵具有O（n 2 ）个元素，并且每个元素必须至少考虑一次用于结果，因此矩阵乘法算法不可能在少于O（n 2 ）个运算中运行。
如果
您可以设计算法，其复杂性仅取决于非零元素的数量。 对于某些问题（例如，有限元方法），这可能是强制性的。
没有！ 我不这么认为。
除非您使用并行处理机器，否则没有办法。 它也有它自己的依赖和限制。
直到现在，它尚未实现。
如果你有n²处理器和共享读存储器架构，你可以在O(n)时间内乘以两个矩阵……但这只是现在的理论。
需要了解更多c/c++开发分享有没有任何方法可以将矩阵乘以O（n）复杂度？，也可以关注C/ C++技术分享栏目—计算机技术网(www.ctvol.com)!
以上就是c/c++开发分享有没有任何方法可以将矩阵乘以O（n）复杂度？相关内容,想了解更多C/C++开发(异常处理)及C/C++游戏开发关注计算机技术网(www.ctvol.com)!)。
本文来自网络收集，不代表计算机技术网立场，如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址：https://www.ctvol.com/c-cdevelopment/979648.html