我想将两个矩阵相乘,但三重循环具有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