矩阵乘法

问题描述

两个 $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{aligned} T(n) = 8 T\left( \frac{n}{2} \right) + \Theta(n^2) \end{aligned}$$

即使如此，计算得到的时间复杂度没有得到改善，仍为 $T(n^3)$。我们可令

于是

这样就把 $8$ 个矩阵相乘转变成 $7$ 个矩阵相乘，时间复杂度降低为

\begin{aligned} T(n) &= 7 T\left( \frac{n}{2} \right) + \Theta(n^2) \ &= \Theta\left(n^{\log _{2}{7}}\right) \end{aligned}