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

核心提示：根据以上结果可得：对于上面这个2×2的例子，使用分而治之算法需要7次乘法和1 8次加/减法运算，c语言算法 - 分而治之算法(3)，而直接使用公式（2 - 1），则需要8次乘法和7次加/减法，这个工作对应于3)，for循环将每一对重量值中较小值和较大值分别与当前的最小值w [ M i n ]和最大值w [

根据以上结果可得：

对于上面这个2×2的例子，使用分而治之算法需要7次乘法和1 8次加/减法运算。而直接使用公式（2 - 1），则需要8次乘法和7次加/减法。要想使分而治之算法更快一些，则一次乘法所花费的时间必须比11次加/减法的时间要长。

假定S t r a s s e n矩阵分割方案仅用于n≥8的矩阵乘法，而对于n<8的矩阵乘法则直接利用公式（2 - 1）进行计算。则n= 8时，8×8矩阵相乘需要7次4×4矩阵乘法和1 8次4×4矩阵加/减法。每次矩阵乘法需花费6 4m+ 4 8a次操作，每次矩阵加法或减法需花费1 6a次操作。因此总的操作次数为7(6 4m+ 4 8a)+ 1 8(1 6a)= 4 4 8m+ 6 2 4a。而使用直接计算方法，则需要5 1 2m+ 4 4 8a次操作。要使S t r a s s e n方法比直接计算方法快，至少要求5 1 2-4 4 8次乘法的开销比6 2 4-4 4 8次加/减法的开销大。或者说一次乘法的开销应该大于近似2 .7 5次加/减法的开销。

假定n<1 6的矩阵是一个“小”问题，S t r a s s e n的分解方案仅仅用于n≥1 6的情况，对于n<1 6的矩阵相乘，直接利用公式（ 2 - 1）。则当n= 1 6时使用分而治之算法需要7(5 1 2m+ 4 4 8a)+1 8(6 4a)= 3 5 8 4m+ 4 2 8 8a次操作。直接计算时需要4 0 9 6m+ 3 8 4 0a次操作。若一次乘法的开销与一次加/减法的开销相同，则S t r a s s e n方法需要7 8 7 2次操作及用于问题分解的额外时间，而直接计算方法则需要7 9 3 6次操作加上程序中执行f o r循环以及其他语句所花费的时间。即使直接计算方法所需要的操作次数比St r a s s e n方法少，但由于直接计算方法需要更多的额外开销，因此它也不见得会比S t r a s s e n方法快。

n 的值越大，Strassen 方法与直接计算方法所用的操作次数的差异就越大，因此对于足够大的n，Strassen 方法将更快。设t(n)表示使用Strassen 分而治之方法所需的时间。因为大的矩阵会被递归地分割成小矩阵直到每个矩阵的大小小于或等于k（k至少为8，也许更大，具体值由计算机的性能决定）.用迭代方法计算，可得t(n)=(nl og27)。因为l og27 ≈2 .8 1，所以与直接计算方法的复杂性(n3)相比，分而治之矩阵乘法算法有较大的改进。

注意事项

分而治之方法很自然地导致了递归算法的使用。在许多例子里，这些递归算法在递归程序中得到了很好的运用。实际上，在许多情况下，所有为了得到一个非递归程序的企图都会导致采用一个模拟递归栈。不过在有些情况下，不使用这样的递归栈而采用一个非递归程序来完成分而治之算法也是可能的，并且在这种方式下，程序得到结果的速度会比递归方式更快。解决金块问题的分而治之算法（例2 - 2）和归并排序方法（ 2 .3节）就可以不利用递归而通过一个非递归程序来更快地完成。

例2-4 [金块问题] 用例2 - 2的算法寻找8个金块中最轻和最重金块的工作可以用二叉树来表示。这棵树的叶子分别表示8个金块（a, b,., h)，每个阴影节点表示一个包含其子树中所有叶子的问题。因此，根节点A表示寻找8个金块中最轻、最重金块的问题，而节点B表示找出a,b,c和d 这4个金块中最轻和最重金块的问题。算法从根节点开始。由根节点表示的8金块问题被划分成由节点B和C所表示的两个4金块问题。在B节点，4金块问题被划分成由D和E所表示的2金块问题。可通过比较金块a和b 哪一个较重来解决D节点所表示的2金块问题。在解决了D和E所表示的问题之后，可以通过比较D和E中所找到的轻金块和重金块来解决B表示的问题。接着在F，G和C上重复这一过程，最后解决问题A。

可以将递归的分而治之算法划分成以下的步骤：

1)从图2 - 2中的二叉树由根至叶的过程中把一个大问题划分成许多个小问题，小问题的大小为1或2。

2)比较每个大小为2的问题中的金块，确定哪一个较重和哪一个较轻。在节点D、E、F和G上完成这种比较。大小为1的问题中只有一个金块，它既是最轻的金块也是最重的金块。

3)对较轻的金块进行比较以确定哪一个金块最轻，对较重的金块进行比较以确定哪一个金块最重。对于节点A到C执行这种比较。

根据上述步骤，可以得出程序1 4 - 1的非递归代码。该程序用于寻找到数组w [ 0 : n - 1 ]中的最小数和最大数，若n < 1，则程序返回f a l s e，否则返回t r u e。

当n≥1时，程序1 4 - 1给M i n和M a x置初值以使w [ M i n ]是最小的重量，w [ M a x ]为最大的重量。

首先处理n≤1的情况。若n>1且为奇数，第一个重量w [ 0 ]将成为最小值和最大值的候选值，因此将有偶数个重量值w [ 1 : n - 1 ]参与f o r循环。当n 是偶数时，首先将两个重量值放在for循环外进行比较，较小和较大的重量值分别置为Min和Max，因此也有偶数个重量值w[2:n-1]参与for循环。

在for循环中，外层if 通过比较确定(w [ i ] , w [ i + 1 ])中的较大和较小者。此工作与前面提到的分而治之算法步骤中的2)相对应，而内层的i f负责找出较小重量值和较大重量值中的最小值和

最大值，这个工作对应于3)。for循环将每一对重量值中较小值和较大值分别与当前的最小值w [ M i n ]和最大值w [ M a x ]进行比较，根据比较结果来修改M i n和M a x（如果必要）。