问题描述
两个 $n \times n$ 的矩阵 $A$ 和 $B$ 相乘，通常算法时间复杂度为 $O(n^3)$。是否存在分治算法可以降低时间复杂度？
问题分析
将 $A$ 和 $B$ 分成 $4$ 个大小为 $\frac{n}{2} \times \frac{n}{2}$ 的子矩阵相乘。
$$ \begin{array}{l} {\left[\begin{array}{ll} C_{11} & C_{12} \\ C_{21} & C_{22} \end{array}\right]=\left[\begin{array}{ll} A_{11} & A_{12} \\ A_{21} & A_{22} \end{array}\right]\left[\begin{array}{ll} B_{11} & B_{12} \\ B_{21} & B_{22} \end{array}\right]} \end{array} $$需要计算的子问题包括 $8$ 个小矩阵乘法以及 $4$ 个矩阵加法，时间复杂度为：
$$ \begin{align*} T(n) = 8 T\left( \frac{n}{2} \right) + \Theta(n^2) \end{align*} $$即使如此，计算得到的时间复杂度没有得到改善，仍为 $T(n^3)$。我们可令
$$ \begin{align*} M_{1} &= A_{11} (B_{12} - B_{22}) \\ M_{2} &= (A_{11} + A_{12}) B_{22} \\ M_{3} &= (A_{21} + A_{22}) B_{11} \\ M_{4} &= A_{22} (B_{21} - B_{11}) \\ M_{5} &= (A_{11} + A_{22}) (B_{11} + B_{22}) \\ M_{6} &= (A_{12} - A_{22}) (B_{21} + B_{22}) \\ M_{7} &= (A_{11} – A_{21}) (B_{11} + B_{12}) \\ \end{align*} $$于是
$$ \begin{align*} C_{11} &= M_{5} + M_{4} - M_{2} + M_{6} \\ C_{12} &= M_{1} + M_{2} \\ C_{21} &= M_{3} + M_{4} \\ C_{22} &= M_{5} + M_{1} – M_{3} – M_{7} \\ \end{align*} $$这样就把 $8$ 个矩阵相乘转变成 $7$ 个矩阵相乘，时间复杂度降低为
\begin{align*} T(n) &= 7 T\left( \frac{n}{2} \right) + \Theta(n^2) \ &= \Theta\left(n^{\log _{2}{7}}\right) \end{align*}