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

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})相乘.但是你可能已经注意到它现在只是一个假设.