# 分而治之| 第 5 組（Strassen 的矩陣乘法） > 原文： [https://www.geeksforgeeks.org/strassens-matrix-multiplication/](https://www.geeksforgeeks.org/strassens-matrix-multiplication/) 給定兩個大小分別為 n x n 的平方矩陣 A 和 B，找到它們的乘法矩陣。 ***樸素的方法*** 以下是將兩個矩陣相乘的簡單方法。 ``` void multiply(int A[][N], int B[][N], int C[][N]) { ????for (int i = 0; i < N; i++) ????{ ????????for (int j = 0; j < N; j++) ????????{ ????????????C[i][j] = 0; ????????????for (int k = 0; k < N; k++) ????????????{ ????????????????C[i][j] += A[i][k]*B[k][j]; ????????????} ????????} ????} } ``` 上述方法的時間復雜度為 O（N ³ ）。 ***分而治之*** 以下是簡單的分而治之方法來將兩個平方矩陣相乘。 1）如下圖所示，將矩陣 A 和 B 劃分為大小為 N / 2 x N / 2 的 4 個子矩陣。 2）遞歸計算以下值。 ae + bg，af + bh，ce + dg 和 cf + dh。 [](https://www.geeksforgeeks.org/wp-content/uploads/strassen_new.png) 在上述方法中，我們對大小為 N / 2 x N / 2 的矩陣進行了 8 次乘法運算，并進行了 4 次加法運算。 兩個矩陣相加需要 `O(n^2)`時間。 所以時間復雜度可以寫成 ``` T(N) = 8T(N/2) + O(N2) From Master's Theorem, time complexity of above method is O(N3) which is unfortunately same as the above naive method. ``` ***簡單分而治之也導致 O（N ³ ），是否有更好的方法？*** 在上述分治法中，高時間復雜度的主要組成部分是 8 個遞歸調用。 **Strassen 方法**的想法是將遞歸調用的數量減少到 7。Strassen 方法類似于上述簡單的分治法，因為該方法還將矩陣劃分為大小為 N /的子矩陣 如上圖所示，為 2 x N / 2，但是在 Strassen 方法中，使用以下公式計算結果的四個子矩陣。 [](https://www.geeksforgeeks.org/wp-content/uploads/stressen_formula_new_new.png) **Strassen 方法的時間復雜度** 兩個矩陣的加法和減法需要 `O(n^2)`時間。 所以時間復雜度可以寫成 ``` T(N) = 7T(N/2) + O(N2) From Master's Theorem, time complexity of above method is O(NLog7) which is approximately O(N2.8074) ``` 通常，出于以下原因，在實際應用中不建議使用 Strassen 方法。 1）Strassen 方法中使用的常數很高，對于典型的應用，樸素方法效果更好。 2）對于稀疏矩陣，有專門針對它們設計的更好方法。 3）遞歸中的子矩陣占用額外的空間。 4）由于非整數值的計算機算法精度有限，因此與自然方法相比，斯特拉森算法中累積的錯誤更大（來源： [CLRS 書](http://www.flipkart.com/introduction-algorithms-3rd/p/itmczynzhyhxv2gs?pid=9788120340077&affid=sandeepgfg)） ``` # Version 3.6 import numpy as np def split(matrix): ????""" ????Splits a given matrix into quarters. ????Input: nxn matrix ????Output: tuple containing 4 n/2 x n/2 matrices corresponding to a, b, c, d ????""" ????row, col = matrix.shape ????row2, col2 = row//2, col//2 ????return matrix[:row2, :col2], matrix[:row2, col2:], matrix[row2:, :col2], matrix[row2:, col2:] def strassen(x, y): ????""" ????Computes matrix product by divide and conquer approach, recursively. ????Input: nxn matrices x and y ????Output: nxn matrix, product of x and y ????""" ????# Base case when size of matrices is 1x1 ????if len(x) == 1: ????????return x * y ????# Splitting the matrices into quadrants. This will be done recursively ????# untill the base case is reached. ????a, b, c, d = split(x) ????e, f, g, h = split(y) ????# Computing the 7 products, recursively (p1, p2...p7) ????p1 = strassen(a, f - h)?? ????p2 = strassen(a + b, h)???????? ????p3 = strassen(c + d, e)???????? ????p4 = strassen(d, g - e)???????? ????p5 = strassen(a + d, e + h)???????? ????p6 = strassen(b - d, g + h)?? ????p7 = strassen(a - c, e + f)?? ????# Computing the values of the 4 quadrants of the final matrix c ????c11 = p5 + p4 - p2 + p6?? ????c12 = p1 + p2??????????? ????c21 = p3 + p4???????????? ????c22 = p1 + p5 - p3 - p7?? ????# Combining the 4 quadrants into a single matrix by stacking horizontally and vertically. ????c = np.vstack((np.hstack((c11, c12)), np.hstack((c21, c22))))? ????return c ``` [記住 Strassen 矩陣方程](https://www.geeksforgeeks.org/easy-way-remember-strassens-matrix-equation/)的簡便方法 **參考**： [算法入門第三版，作者：Clifford Stein，Thomas H. Cormen，Charles E. Leiserson，Ronald L.Rivest](http://www.flipkart.com/introduction-algorithms-3rd/p/itmczynzhyhxv2gs?pid=9788120340077&affid=sandeepgfg) [https：// www.youtube.com/watch?v=LOLebQ8nKHA](https://www.youtube.com/watch?v=LOLebQ8nKHA) [https://www.youtube.com/watch?v=QXY4RskLQcI](https://www.youtube.com/watch?v=QXY4RskLQcI)