Rosun_ 于 2016-09-28 17:45:08 发布Strassen算法之矩阵乘法
问题：给定两个n-by-n矩阵A和B，计算C=AB；
分析：如果采用一般方法求解矩阵C，我们根据乘法定义知道C中每个元素都需要O(n)次乘法，总共有n^2个元素，所以时间复杂度是O(n^3)。当n很大时，这个时间是非常久的。那我们有什么快速的方法计算矩阵乘法呢？采用Divide、Conquer and Combine思想，把矩阵A、B、C分别画成4个小矩阵，这样.把每个问题分成8个子问题和4次加法。到此，这是分治策略的方法，时间复杂度也是O(n^3)。但实际上我们不需要计算8个子问题，值需要计算7个矩阵的结果就能表示出来。
(C11C12C21C22)=(a11a12a21a22)
