《Algorithms Part 1》第二周問題集（2）multiply matrices

02-02

1. 先來回顧一下矩陣乘法

2. 矩陣乘法的時間複雜度是？

$O(n^{3} )$ ，一共有 $n^{2}$ 個元素，每個元素需要n次乘法和n次加法。n

3. 那我們來試試用divide and conquer

也就是矩陣分塊乘法

但是這樣時間複雜度並沒有降低，依然是 $O(n^{3} )$

4. 看來divide and conquer也不是隨便的divide啊，那怎麼辦呢？

Strassen的方法可以把8次遞歸降低到7次，那這不是僅僅降低了12.5%的時間嘛，不是，具體是多少留待講到master method的時候再說。

69年Strassen發明出該演算法的時候可是震驚了很多人，因為很多人認為沒有比 $O(n^{3} )$ 更好的演算法了。

是哪7個乘積這麼神奇？

為什麼是這7個乘積呢？能不能縮減到6個？5個？

參考資料：

計算機演算法：Strassen矩陣相乘演算法-圖靈社區

Strassen algorithm

http://www.stoimen.com/blog/2012/11/26/computer-algorithms-strassens-matrix-multiplication/