文档介绍：计算机算法 ——设计与分析导论
南开大学计算机科学与技术系
刘璟
1
Chapter 3. 分治技术 (Divide and Conquer)
分治策略的思想
大整数乘法
矩阵相乘的Strassen算法
选择(Selection)问题的线性算法
2
分治策略的思想
分治算法把一个规模为n的问题实例划分为若干个规模较小的子问题:其规模分别为
然后递归地解这k个子问题,最后把k个子结果合并为整个问题的解。
分治算法的几个要点是:
递归基础:
为了保证递归过程在有限步骤内结束,当n值小于某常数 n0 时,要有一个简单的处理算法。
3
划分:
分治把长为n的问题实例分成几个部分。许多分治算法简单地取k = 2。为了算法有好的性能,划分应该尽量平衡。
递归:
就是用同样的方法去解各个子问题。如果k个子问题的长度为n1,n2,…,nk ,那么算法执行的总代价和各个子问题的代价应分别为T(n)和T(n1),T(n2),..,T(nk)。
合并结果:
几个子问题获得解决之后,各个结果应合并为整个问题的解。解的合并的代价因情况不同而异。
4
大整数乘法
选择排序(Selection Sorting)
设Х和Y是两个n位的二进制数,按传统方法计算乘积Х·Y,需要O(n2)次位运算。
为简化问题,设n = 2k,k为正整数。
当n = 1时,计算Х·Y就是一次位乘。对Х、Y进行划分:
X = A · 2n/2 + B
Y = C · 2n/2 + D
A, B, C, D为 n/2 位的二进制数。
A
B
C
D
X:
Y:
5
则有:
Х·Y = AC·2n + ( AD + BC ) ·2n/2 + BD
按上式可以把计算Х·Y的问题划分为四个子问题。即计算n/2位的二进制数的乘积AC,AD,BC,BD。用同样方式计算完成之后,再通过三次n/2位的加法和两次移位,合并为Х·Y。显然,合并代价为O(n)阶。
因此得到递归方程如下:

根据主项定理得:
()
()
6
与我们所期望的不同,简单的分治策略未达到改进的目的。事实上,把一个n位数乘法化为4次n/2位数乘法是不可能改进O(n2)的复杂度的。幸运的是,Х·Y可以有另一计算公式:
X·Y = AC·2n + [ (A-B)(D-C) + BD + AC ] ·2n/2 + BD
、BD和(A-B)(D-C)三次n/2位数的乘法,其合并代价稍有增加,6次加减法、2次移位,仍为O(n)阶。时间复杂度的递归方程为:
()
()
7
方程的解为:
这个算法的设计过程指明:
1. 分治策略用于算法设计,往往需要一些技巧。
2. 表面上分治只是把一个大问题分成几个子问题,分别计算然后再合并为问题的解,似乎没有明显的节省,但效果却很显著。对于最大元最小元问题,分治策略把计算代价从2n – 3减为3n/2 – 2,大致减少了1/4的工作量;而在n位数乘问题中,代价从O(n2)减少到O(),当n较大时,可能会成倍的减速,,在n = 1000时,它大于16。
8
矩阵相乘的Strassen算法
问题
矩阵运算中,矩阵的元素一般为整型和实型,其基本操作是实数或整数乘法,当数的有效数字位数较多时,数的加法较数的乘法占用时间较少。
已知:n阶矩阵A, B,计算乘积C = A · B,计算公式为:
其中cij,aij,bij为矩阵C,A,B的元素。
显然,完成计算共需n3次乘法和n2(n-1)次加法。
()
9
分治
为了简化问题,设 n = 2k,k为正整数。
直接把矩阵A,B,C一分为四,化为n/2阶矩阵:
矩阵乘积C = A·B分解为:
()
10