是否有有O（n）的复杂性矩阵相乘任何方法？ [英] Is there any method for multiplying matrices having O(n) complexity?

问题描述

我想将两个矩阵相乘，但三环为O（N ³ ）的复杂性。是否有动态规划的算法，将两个矩阵相乘为O（n）的复杂性？

I want to multiply two matrices but the triple loop has O(n³) complexity. Is there any algorithm in dynamic programming to multiply two matrices with O(n) complexity?

那么好吧，我们不能为O得到最好的（N ^2.81 ）

ok fine we can't get best than O(n^2.81 )

编辑：，但那里甚至可以接近的结果高达某些特定的没有任何解决方案。列和矩阵的行

edit: but is there any solution that can even approximate the result upto some specific no. of columns and rows of matrix

我的意思是我们得到的最好的O（N ^2.81 ）有一个复杂的解决方案，但完美的结果，但如果有一个连矩阵乘法的近似值，因为我们有阶乘的近似公式的任何解决方案等等。

i mean we get the best of O(n^2.81 ) with a complex solution but perfect results but if there is any solution for even an approximation of multiplication of matrices as we have formulas for factorial approximation etc.

如果有任何你知道它会帮助我

if there is any you know it will help me

问候。

推荐答案

在最迄今已知矩​​阵相乘算法是在的铜匠-威诺格拉德算法 是为O（n ^2.38 ）的复杂性，但它是的不的用于实际用途。

The best Matrix Multiplication Algorithm known so far is the "Coppersmith-Winograd algorithm" with O(n^2.38 ) complexity but it is not used for practical purposes.

然而，你可以随时使用 Strassen的算法 有 O（ ñ ^2.81 ）的复杂性，但没有这样的已知算法与O（n）的复杂性矩阵乘法。

However you can always use "Strassen's algorithm" which has O(n^2.81 ) complexity but there is no such known algorithm for matrix multiplication with O(n) complexity.

这篇关于是否有有O（n）的复杂性矩阵相乘任何方法？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！