Strassen's method

^{Matrix Multiplication Problem：}

        ^{Let A、Band C by n x n matrix and C = A x B}

        ^{要解決Matrix Multiplication Problem的algorithm大致有三種：
        1、Straightforward method
        2、Divide-and-conquer strategy
        3、Strassen's method}

        ^{其演算法分述如下：}

^{（1）Straightforward method}

^{Elements of matrix C is got by}

           ^式3.1

^{因為結果矩陣C中共有n2個元素，而每一個元素均需矩陣A與矩陣B中的n個元素進行n次乘法運算（O(n)），因此Straightforward method的Time Complexity計算如下：}

  ^{O(n) x n2 = O(n3)}

^{（2）Divide-and-conquer strategy}

         ^式3.2

^{也就是分別將矩陣A、B與C分別切割成四部分，而結果矩陣C的四個部分分別可由矩陣A及矩陣B的四部分相乘得之，其公式如上所述。}

^{Divide-and-conquer strategy的Time Complexity分析如下：}

^{從式3.1中可以得知，欲求的結果矩陣C的四個部分，分別需由矩陣A及矩陣B的四部分進行8次乘法及4次加法運算，而乘法及加法運算過程中矩陣的size均是n/2，假設Divide-and-conquer strategy的Time Complexity是T(n)，則：}

^{乘法運算部分：8T(n/2)}

^{加法運算部分：n/2 x n/2 x 4 = O(n2)}

^=> 

^=> 

^{=> 與Straightforward method的time complexity相同}

^{（3）Strassen's method}

  ^{在Divide-and-conquer strategy中，共須8個乘法運算及4個加法運算；然而在Strassen's method中，共須7個乘法運算及18個加法運算，假設Strassen's method的Time Complexity是T(n)，則：}

^{乘法運算部分：7T(n/2)}

^{加法運算部分：n/2 x n/2 x 4 = O(n2)}

^=> 

^=> 

        ^{由以上演算法分析得知，三種方法之執行時間比較為Straightforward method  Divide-and-conquer strategy> Strassen's method。}