Question

矩阵乘法的最小时间复杂度是多少

Answer 1

假设矩阵A为n*m,矩阵B为m*n ,则AxB,如下计算过程：
1.矩阵A中第一行的元素与矩阵B的第一列元素对应相乘,得
结果第一行的第一个元素要进行m次乘法运算,故总的需要m*n*m次乘法运算.
2.计算时间复杂度.
即大O,运行上限.故O(n^3)

Answer 2

1. C_(n×n)= A_(n×n)∙B_(n×n)当n是2的幂时可以采用分治的方法。如果把矩阵分成2x2的子矩阵乘法，strassen方法可以达到Θ(n^2.81). 目前，最好的计算时间上界是O(n^2.376).