c – 如何在时间复杂度方面优化cpp中的矩阵乘法？

概述鉴于任何2个matrics a和b(没有特殊属性),我们有更好的计算乘法的方法吗？ for(i=0; i<r1; ++i)for(j=0; j<c2; ++j)for(k=0; k<c1; ++k){ mult[i][j]+=a[i][k]*b[k][j];} 如果你好奇它们是否存在于理论中,那么是的.例如,Strassen算法(见 https://en.wikipedia.org 鉴于任何2个matrics a和b(没有特殊属性),我们有更好的计算乘法的方法吗？

for(i=0; i<r1; ++i)for(j=0; j<c2; ++j)for(k=0; k<c1; ++k){    mult[i][j]+=a[i][k]*b[k][j];}

解决方法 如果你好奇它们是否存在于理论中,那么是的.例如,Strassen算法(见 https://en.wikipedia.org/wiki/Strassen_algorithm).它甚至不是我们所知道的最快的.就我而言,目前最好的是coppersmith-Winograd算法(见 https://en.wikipedia.org/wiki/Coppersmith%E2%80%93Winograd_algorithm),它类似于O(n ^ {2.37})(Strassen的时间复杂度类似于O(n ^ {2.8}).

但实际上它们比你编写的更难实现,并且它们在O()下隐藏了非常大的时间常数,所以你写的O(n ^ 3)算法在n值较低时更好,更容易实现.

还有一个Strassen的假设,声称对于每个eps> 0有一种算法将两个矩阵与时间复杂度O(n ^ {2 eps})相乘.但是你可能已经注意到它现在只是一个假设.

总结

以上是内存溢出为你收集整理的c – 如何在时间复杂度方面优化cpp中的矩阵乘法？全部内容，希望文章能够帮你解决c – 如何在时间复杂度方面优化cpp中的矩阵乘法？所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。