【算法导论】strassen算法：比较快的矩阵乘法算法

本文主要是介绍【算法导论】strassen算法：比较快的矩阵乘法算法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

考虑两个 n 级矩阵 A, B, 矩阵 C = A * B. 则有$c_{ij}={\sum }_{k=1}^n{a}_{ij}\ast b_{kj}$.
对于两个矩阵相乘的问题，我们给出三个解决办法：迭代算法、简单分治算法、strassen分治算法。

---

解法一：迭代算法，即使用三层循环，这是最简单的算法，其代码如下：

void matrix_multiply( vector<vector<int>>& A, vector<vector<int>>& B, vector<vector<int>>& C){// A, B, C 均为 n * n 矩阵，且 C[i][j] = 0;for( int i = 0; i < A.size(); i++)for(int j = 0; j < A.size(); j++)for( int k = 0; k < A.size(); k++)C[i][j] += A[i][k]* B[k][j];
}

测试用例：

算法分析：由于使用了三层循环，得到其时间复杂度为$O(n^3)$.

---

方法二：简单的分治算法
利用分块矩阵计算矩阵乘法。
对于 n 级矩阵A, 我们可以将其划分为 4 个 n/2 级矩阵，例如：
$$A_{n\ast n}=\left(\begin{array}{cc}{A}_{11}& A_{12}\\ A_{21}& A_{22}\end{array}\right)$$

同理，有
$$B_{n\ast n}=\left(\begin{array}{cc}{B}_{11}& B_{12}\\ B_{21}& B_{22}\end{array}\right),C_{n\ast n}=\left(\begin{array}{cc}{C}_{11}& C_{12}\\ C_{21}& C_{22}\end{array}\right)$$
则 C = AB 可以改写为：
( C 11 C 12 C 21 C 22 ) = ( A 11 A 12 A 21 A 22 ) ( B 11 B 12 B 21 B 22 ) \begin{pmatrix} C_{11} & C_{12} \\ C_{21} & C_{22} \\ \end{pmatrix} = \begin{pmatrix} A_{11} & A_{12} \\ A_{21} & A_{22} \\ \end{pmatrix} \begin{pmatrix} B_{11} & B_{12} \\ B_{21} & B_{22} \\ \end{pmatrix} (C

这篇关于【算法导论】strassen算法：比较快的矩阵乘法算法的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---