用Eigin做矩阵相乘，计算时间太久是因为什么？

Question

这是代码：

int main()
{
time_t start,end,time;
MatrixXf M=MatrixXf::Random(50,50);
MatrixXf N=MatrixXf::Random(50,50);
start=clock();
MatrixXf S=M*N;
end=clock();
time=end-start;
cout<<"S=\n"<<S<<endl;
cout<<time<<"ms\n"<<endl;

}

矩阵大小 数据类型为float Eigen库运算时间 单位：ms
50*50 20
100*100 160
200*200 1260
300*300 4312
500*500 19665

Answer 1

很明显，你现在的算法复杂度是n^3

这是很正常的。

时间复杂度
正如我以上提到的，Strassen算法仅仅比通用矩阵相乘算法好一点点。通用矩阵相乘算法时间复杂度是O(n^3)，然而Strassen算法复杂度则是O(n^2.80)。
你能在下图观察到，随着n的变大，Strassen算法是如何比通用矩阵相乘算法变得更有效率的。

http://www.ituring.com.cn/article/17978