3.3 分治法的应用

下面通过一些例子来直观地感受应用分治思想解决实际问题。

例3.4 通过简单分治法求矩阵乘法。

问题描述： n×n矩阵A和B的乘积矩阵C中的元素C[i,j]定义为：

如果依此定义来计算矩阵A和B的乘积矩阵C，则每计算C的一个元素C[i,j]，就需要做n次乘法和n-1次加法。因此，算出矩阵C的n²个元素所需的计算时间为O(n³)。

下面用分治法来求两个矩阵的乘法。

首先假定n是2（n=2^k）的幂，如果相乘的两矩阵A和B不是方阵，可以通过适当添加全零行和全零列，使之成为行列数为2的幂的方阵。

使用分治法，将矩阵A、B和C中每一矩阵都分块成4个大小相等的子矩阵，每个子矩阵都是n/2×n/2的方阵。由此可将方程C=A×B重写为：

由此可得：

C ₁₁=A₁₁B₁₁+A₁₂B₂₁

C ₁₂=A₁₁B₁₂+A₁₂B₂₂

C ₂₁=A₂₁B₁₁+A₂₂B₂₁

C ₂₂=A₂₁B₁₂+A₂₂B₂₂

如果n=2，则两个2阶方阵的乘积可以直接计算出来，共需8次乘法和4次加法。

当子矩阵的阶大于2时，可以继续将子矩阵分块，直到子矩阵的阶降为2。这样就产生了一个分治降阶的递归算法。依此算法，可以将计算2个n阶方阵的乘积转化为计算8个n/2阶方阵的乘积和4个n/2阶方阵的加法。2个n/2×n/2矩阵的加法显然可以在c*n²/4（O(n²)）时间内完成，这里c是一个常数。

上述分治法的计算时间耗费T(n)的递归方程满足：

可得T(n)=O(n³)，相比依照定义计算的方法没有改进，原因是没有减少矩阵乘法次数。为了降低时间复杂度，必须减少乘法次数，其关键在于计算2个2阶方阵的乘积时所用乘法次数能否少于8次。为此，Strassen提出了一种只用7次乘法运算计算2阶方阵乘积的方法（但增加了加/减法次数）：

M ₁=A₁₁(B₁₂-B₂₂)，M₂=(A₁₁+A₁₂)B₂₂

M ₃=(A₂₁+A₂₂)B₁₁，M₄=A₂₂(B₂₁-B₁₁)

M ₅=(A₁₁+A₂₂)(B₁₁+B₂₂)，M₆=(A₁₂-A₂₂)(B₂₁+B₂₂)

M ₇=(A₁₁-A₂₁)(B₁₁+B₁₂)

完成了这7次乘法后，再做若干次加/减法就可以得到：

C ₁₁=M₅+M₄-M₂+M₆，C₁₂=M₁+M₂

C ₂₁=M₃+M₄，C₂₂=M₅+M₁-M₃-M₇

在这种分治算法中，用了7次对于n/2阶矩阵乘积的递归调用和18次n/2阶矩阵的加减运算。由此可知，该算法的所需的计算时间T(n)满足如下的递归方程：

求解可得：T(n)=O(n^log7)≈O(n^2.81)，相较T(n)=O(n³)有了较大的改进。

关于空间复杂度，常规方法需要存储2个n阶方阵，加一行n个存储单元共需2n²+n个单元。而Strassen方法需要O(n^2.81)个单元，比常规乘法大，因此Strassen方法可以看作以空间换时间的一种方法。

例3.5 使用分治法求解智力题。

假设有一个袋子，袋子中装有15个1元硬币和一个游戏币，这个游戏币比1元硬币要轻一些，如何不通过观察外观的方式找出那个游戏币呢？本题提供一个天平用于称量。通过逐个称量硬币质量的方法固然可以找出这个游戏币，但是这样需要15次称量，即使是将硬币分为8组，每组2个，每组比较一次，如果发现轻的，则能确定该币为游戏币，此种方法最少也需要8次称量。无论以上哪种方法，都不是最优方法。而采用分治法，问题就变得简单高效了。第一次将16个硬币平均分为两组，每组8个硬币，比较一次，找出质量较轻的一组8个硬币，根据性质可知，那枚游戏币肯定在质量较轻的这一组中。然后再将这8个硬币平均分为两组，每组4个硬币，找出质量较轻的一组4个硬币，紧接着将这4个硬币平均分为两组，每组2个硬币，找出质量较轻的一组2个硬币，最后，将两个硬币分别放在天平两端，即可找出这枚游戏币来。此种方法一共只需要进行4次比较即可。将硬币分为两组后，一次比较可以将硬币的范围缩小到原来的一半，这样充分地利用了只有一枚游戏币的基本性质。

不难发现，分治法的应用范围非常广泛，除上面讲的一些例子以外，常见的应用场景还有：1）二分查找，2）大整数乘法，3）棋盘覆盖，4）归并排序，5）快速排序，6）线性时间选择，7）最接近点对问题，8）循环赛日程表，9）最大子段和等，在此就不一一介绍了。