c语言算法 - 分而治之算法

例2-3 [矩阵乘法] 两个n×n阶的矩阵A与B的乘积是另一个n×n阶矩阵C，C可表示为假如每一个C(i, j)都用此公式计算，则计算C所需要的操作次数为n3 m+n2(n- 1)a，其中m表示一次乘法，a 表示一次加法或减法。

为了得到两个矩阵相乘的分而治之算法，需要：1)定义一个小问题，并指明小问题是如何进行乘法运算的； 2)确定如何把一个大的问题划分成较小的问题，并指明如何对这些较小的问题进行乘法运算； 3)最后指出如何根据小问题的结果得到大问题的结果。为了使讨论简便，假设n 是2的幂（也就是说， n是1，2，4，8，1 6，.）。

首先，假设n= 1时是一个小问题，n> 1时为一个大问题。后面将根据需要随时修改这个假设。对于1×1阶的小矩阵，可以通过将两矩阵中的两个元素直接相乘而得到结果。

考察一个n> 1的大问题。可以将这样的矩阵分成4个n/2×n/2阶的矩阵A1，A2，A3，和A4。当n 大于1且n 是2的幂时，n/2也是2的幂。因此较小矩阵也满足前面对矩阵大小的假设。矩阵Bi和Ci 的定义与此类似.

根据上述公式，经过8次n/2×n/2阶矩阵乘法和4次n/2×n/2阶矩阵的加法，就可以计算出A与B的乘积。因此，这些公式能帮助我们实现分而治之算法。在算法的第二步，将递归使用分而治之算法把8个小矩阵再细分（见程序2 - 1 9）。算法的复杂性为(n3)，此复杂性与程序2 - 2 4直接使用公式（2 - 1）所得到的复杂性是一样的。事实上，由于矩阵分割和再组合所花费的额外开销，使用分而治之算法得出结果的时间将比用程序2 - 2 4还要长。

为了得到更快的算法，需要简化矩阵分割和再组合这两个步骤。一种方案是使用S t r a s s e n方法得到7个小矩阵。这7个小矩阵为矩阵D, E, ., J，矩阵D到J可以通过7次矩阵乘法， 6次矩阵加法，和4次矩阵减法计算得出。前述的4个小矩阵可以由矩阵D到J通过6次矩阵加法和两次矩阵减法得出.

用上述方案来解决n= 2的矩阵乘法。将某矩阵A和B相乘得结果C，如下所示：

因为n> 1，所以将A、B两矩阵分别划分为4个小矩阵，每个矩阵为1×1阶，仅包含一个元素。1×1阶矩阵的乘法为小问题，因此可以直接进行运算。利用计算D～J的公式，得：

D= 1（6-8）=-2

E= 4（7-5）= 8

F=（3 + 4）5 = 3 5

G=（1 + 2）8 = 2 4

H=（3-1）（5 + 6）= 2 2

I=（2-4）（7 + 8）=-3 0

J=（1 + 4）（5 + 8）= 6 5