【有书共读】《算法导论》第4章 - 分治策略 读书笔记（中）
矩阵乘法的Strassen算法
若A=(aij)和B=(bij)是n×n的方阵，则对i，j=1，2，3，…，n，定义乘积C=A•B中的元素cij为：
我们很容易得到一个执行时间为Θ(n3)的算法来计算矩阵乘法，因为矩阵乘法的的自然定义就需要进行这么多次的标量乘法。然而实际上，我们有方法在o(n3)时间内完成矩阵乘法：Strassen的著名n×n矩阵相乘的递归算法。后面它将被证明运行时间为Θ(nlg7)——渐近复杂性优于简单的矩阵乘法过程。
一个简单的分治算法
假定将A、B和C均分解为4个n/2×n/2的子矩阵：
因此可以将公式C=A•B改写为：
等价于如下4个公式：
于是根据上面4个公式我们很容易设计一个直接的递归分治算法。值得注意的是，我们在分解矩阵时，并不需要复制矩阵元素，可以直接使用下标运算来节省一些时间（虽然对总渐近运行时间并无影响）。
这个简单的分治算法的运行时间的递归式：
后面我们将看到利用主方法求解递归式，得到的解为T(n)=Θ(n3)。也就是说简单的分治算法并不优于直接的矩阵乘法过程。
Strassen方法
Strassen算法包含4个步骤：
- 将矩阵A、B和C做如上分解
- 创建如下10个n/2×n/2的矩阵：
- 递归计算7个矩阵积：
- 计算矩阵C的子矩阵：
将上面的几个公式展开我们很容易证明上面4个步骤确实生成了正确的矩阵乘积。当n>1时，步骤1、2和4共花费Θ(n2)时间，步骤3要求进行7次n/2×n/2矩阵的乘法。因此，我们得到如下描述Strassen算法时间T(n)的递归式：
我们用常数次矩阵加法的代价减少了一次矩阵乘法。这种交换确实能带来更低的渐近运行时间。之后我们会看到，这个递归式的解为T(n)=Θ(nlg7)。
#笔记##读书笔记#
投递美团等公司7个岗位 >