给定两个大小为n × n的矩形A和B,计算它们的乘积。

朴素方法

下面是将两个矩阵相乘的朴素方法

void multiply(int A[][N], int B[][N], int C[][N]) {
  for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
      C[i][j] = 0;
      for (int k = 0; k < N; k++)
        C[i][j] += A[i][k] * B[k][j];
    }
  }
}

上述方法的时间复杂度是$O(N^3)$

分治

以下是简单的将两个矩阵相乘的分治算法

  1. 如下图所示,将矩阵$A$和$B$分成$4$个大小为$N / 2 \times N / 2$的子矩阵。
  2. 递归地计算$ae + bg, af + bh, ce + dg$和$cf + dh$

在上面的方法中,我们对大小为$N / 2 \times N / 2$的矩阵进行了8​​次乘法和4次加法。将两个矩阵相加需要$O(N^2)$的时间。所以时间的复杂性可以写成

$T(N) = 8T(N / 2) + O(N^2)$

根据主定理,上面算法的时间复杂度为$O(N^3)$,很不幸地和朴素的方法一样……

简单的分治算法也是$O(N^3)$的,有没有更好的方法?

在上述分治法中,时间复杂度高的主要成分是8次递归调用。Strassen算法的思想是将递归调用的数量减少到7。Strassen的方法类似于上面简单的分治算法,就是说这种算法也像上图那样将矩阵划分为大小为$N / 2 \times N / 2$的子矩阵,但在Strassen方法中,结果的4个子矩阵使用以下公式计算。

 

Strassen算法的时间复杂度

两个矩阵的加法和减法都需要$O(N^2)$的时间,所以时间复杂度可以写成

$T(N) = 7T(N / 2) + O(N^2)$

根据主定理,上面算法的时间复杂度为$O(N{log7})$,大约是$O(N{2.8074})$

由于以下原因,Strassen算法通常不适用于实际应用。

  1. Strassen算法的常数很大,对于典型应用,朴素方法效果更好。
  2. 对于稀疏矩阵,有专门为他们设计的更好方法。
  3. 递归中的子矩阵需要额外的空间。
  4. 由于计算机算法对非整数值的精度有限,Strassen算法的累积误差比朴素方法要大(资料来源:算法导论)