## 題目描述 請編程實現矩陣乘法，并考慮當矩陣規模較大時的優化方法。 ## [](https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/zh/02.08.md#分析與解法)分析與解法 根據wikipedia上的介紹：兩個矩陣的乘法僅當第一個矩陣A的行數和另一個矩陣B的列數相等時才能定義。如A是m×n矩陣，B是n×p矩陣，它們的乘積AB是一個m×p矩陣，它的一個元素其中 1 ≤ i ≤ m, 1 ≤ j ≤ p。 [](https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/images/41~42/42.1.png) 值得一提的是，矩陣乘法滿足結合律和分配率，但并不滿足交換律，如下圖所示的這個例子，兩個矩陣交換相乘后，結果變了： [](https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/images/41~42/42.1-2.png) 下面咱們來具體解決這個矩陣相乘的問題。 ### [](https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/zh/02.08.md#解法一暴力解法)解法一、暴力解法 其實，通過前面的分析，我們已經很明顯的看出，兩個具有相同維數的矩陣相乘，其復雜度為O(n^3)，參考代碼如下： ~~~ //矩陣乘法，3個for循環搞定 void MulMatrix(int** matrixA, int** matrixB, int** matrixC) { for(int i = 0; i < 2; ++i) { for(int j = 0; j < 2; ++j) { matrixC[i][j] = 0; for(int k = 0; k < 2; ++k) { matrixC[i][j] += matrixA[i][k] * matrixB[k][j]; } } } } ~~~ ### [](https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/zh/02.08.md#解法二strassen算法)解法二、Strassen算法 在解法一中，我們用了3個for循環搞定矩陣乘法，但當兩個矩陣的維度變得很大時，O（n^3）的時間復雜度將會變得很大，于是，我們需要找到一種更優的解法。 一般說來，當數據量一大時，我們往往會把大的數據分割成小的數據，各個分別處理。遵此思路，如果丟給我們一個很大的兩個矩陣呢，是否可以考慮分治的方法循序漸進處理各個小矩陣的相乘，因為我們知道一個矩陣是可以分成更多小的矩陣的。 如下圖，當給定一個兩個二維矩陣A B時： [](https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/images/41~42/42.2.png) 這兩個矩陣A B相乘時，我們發現在相乘的過程中，有8次乘法運算，4次加法運算： [](https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/images/41~42/42.3.png) 矩陣乘法的復雜度主要就是體現在相乘上，而多一兩次的加法并不會讓復雜度上升太多。故此，我們思考，是否可以讓矩陣乘法的運算過程中乘法的運算次數減少，從而達到降低矩陣乘法的復雜度呢？答案是肯定的。 1969年，德國的一位數學家Strassen證明O(N^3)的解法并不是矩陣乘法的最優算法，他做了一系列工作使得最終的時間復雜度降低到了O(n^2.80)。 他是怎么做到的呢？還是用上文A B兩個矩陣相乘的例子，他定義了7個變量： [](https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/images/41~42/42.4.png) 如此，Strassen算法的流程如下： * 兩個矩陣A B相乘時，將A, B, C分成相等大小的方塊矩陣： [](https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/images/41~42/42.5.png) * 可以看出C是這么得來的： [](https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/images/41~42/42.6.jpeg) * 現在定義7個新矩陣（_讀者可以思考下，這7個新矩陣是如何想到的_）： [](https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/images/41~42/42.7.jpeg) * 而最后的結果矩陣C 可以通過組合上述7個新矩陣得到： [](https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/images/41~42/42.8.jpeg) 表面上看，Strassen算法僅僅比通用矩陣相乘算法好一點，因為通用矩陣相乘算法時間復雜度是[](https://camo.githubusercontent.com/aeef0df9107adbd6463c9e4fe6748f7815dec922/687474703a2f2f6c617465782e636f6465636f67732e636f6d2f6769662e6c617465783f2537426e253545333d6e2535452537426c6f675f3238253744253744)，而Strassen算法復雜度只是?[](https://camo.githubusercontent.com/f7e265e7402a954d8853d9724b203e0f648a12bf/687474703a2f2f6c617465782e636f6465636f67732e636f6d2f6769662e6c617465783f2537424f286e2535452537426c6f675f3237253744293d4f286e253545253742322e38303725374429253744)。但隨著n的變大，比如當n >> 100時，Strassen算法是比通用矩陣相乘算法變得更有效率。 如下圖所示： [](https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/images/41~42/42.9.png) 根據wikipedia上的介紹，后來，Coppersmith–Winograd 算法把 N* N大小的矩陣乘法的時間復雜度降低到了：[](https://camo.githubusercontent.com/3828207037dbef5a343930907319c428337e9443/687474703a2f2f6c617465782e636f6465636f67732e636f6d2f6769662e6c617465783f2537424f286e253545253742322e33373534373725374429253744)，而2010年，Andrew Stothers再度把復雜度降低到了[](https://camo.githubusercontent.com/b4ca1c880f8008d0063ab91cd95d8271dd5846e1/687474703a2f2f6c617465782e636f6465636f67732e636f6d2f6769662e6c617465783f2537424f286e253545253742322e3337333625374429253744)，一年后的2011年，Virginia Williams把復雜度最終定格為：[](https://camo.githubusercontent.com/9e7e3d9b8139728ee592e2b6dc0f3ed69605b6d0/687474703a2f2f6c617465782e636f6465636f67732e636f6d2f6769662e6c617465783f2537424f286e253545253742322e3337323725374429253744)。