[理学]《算法设计与分析》第05章课件(PPT 103页).pptx

1、第1页，共103页。第2页，共103页。第3页，共103页。第4页，共103页。第5页，共103页。顾名思义就是分而治之。一个问题能够顾名思义就是分而治之。一个问题能够用分治法求解的要素是：第一，问题能够按照某用分治法求解的要素是：第一，问题能够按照某种方式分解成若干个规模较小、相互独立且与原种方式分解成若干个规模较小、相互独立且与原问题类型相同的子问题；第二，子问题足够小时问题类型相同的子问题；第二，子问题足够小时可以直接求解；第三，能够将子问题的解组合成可以直接求解；第三，能够将子问题的解组合成原问题的解。原问题的解。由于分治法要求分解成同类子问题，并允许不由于分治法要求分解成同类子问题，

2、并允许不断分解，使问题规模逐步减小，最终可用已知的断分解，使问题规模逐步减小，最终可用已知的方法求解足够小的问题，因此，分治法求解很自方法求解足够小的问题，因此，分治法求解很自然导致一个递归算法。然导致一个递归算法。第6页，共103页。分治法分治法SolutionType DandC(ProblemType P)ProblemType P1，P2，Pk;if(Small(P)return S(P);else Divide(P，P1，P2，Pk);Return Combine(DandC(P1)，DandC(P2)，DandC(Pk);第7页，共103页。一分为二的分治法一分为二的分治法Solu

3、tionType DandC(int left，int right)if(Small(left,right)return S(left,right);else int m=Divide(left，right);Return Combine(DandC(left，m)，DandC(m+1，right);第8页，共103页。采用分治法求解问题通常得到一个递归算法。如果较大采用分治法求解问题通常得到一个递归算法。如果较大的问题被分解成同样大小的几部分，那么分析相应算法的的问题被分解成同样大小的几部分，那么分析相应算法的执行时间，往往可得到如下的递推关系式：执行时间，往往可得到如下的递推关系式：T(n

4、)=aT(n/b)+cnk，T(1)=c 第9页，共103页。设设a,b,c和和k为常数，为常数，T(n)=aT(n/b)+cnk，T(1)=c，则，则，kkkkkalogba )n(ba )nlogn(ba )n()n(Tb如果如果如果如果如果如果 第10页，共103页。miikmmiikimkkkmmmkkkkkkkkkkkabcabaccnbnacbncaTacnbnacbncabnTacnbnacbncbnaTacnbnacbnTacnbncbnaTacnbnaTnT00112233232222)/()/()/()1()/()/()/()/()/()/()/()/()/()/()/()

5、(第11页，共103页。设设r=bk/a，下面分三种情况计算，下面分三种情况计算。（1）若）若r1，则，则 所以所以 )r1/(1rm0ii )(nT(n)alogb nlog1m1r bm0ii )nlogn()nlog(nT(n)kalogb )r(1r1rr m1mm0ii )n()b()r(aT(n)kmkmm 第12页，共103页。kkkkkalogba )n(ba )nlogn(ba )n()n(Tb如如果果如如果果如如果果 第13页，共103页。template struct E/可排序表中元素的类型可排序表中元素的类型operator K()const return key;/

6、重载类型转换运算符重载类型转换运算符K key;/关键字可以比较大小关键字可以比较大小D data;/其他数据其他数据;第14页，共103页。class SortableList /可排序表类可排序表类 public:SortableList(int mSize)/构造函数构造函数 maxSize=mSize;l=new TmaxSize;n=0;SortableList()delete l;/析构函数析构函数 private:T*l;/定义动态一维数组定义动态一维数组int maxSize;/线性表的最大表长线性表的最大表长int n;/线性表的实际长度线性表的实际长度;第15页，共103页

7、。第16页，共103页。在一个元素集合中寻找最大元素和最小元在一个元素集合中寻找最大元素和最小元素的问题。素的问题。第17页，共103页。template void SortableList:MaxMin(T&max,T&min)const if(n=0)return;max=min=l0;for(int i=1;imax)max=li;if(limin)min=li;/第18页，共103页。template void SortableList:MaxMin(T&max,T&min)const if(n=0)return;max=min=l0;for(int i=1;imax)max=li;e

8、lse if(limin)min=li;第19页，共103页。template void SortableList:MaxMin(int i,int j,T&max,T&min)const T min1,max1;if(i=j)max=min=li;else if(i=j-1)if(lilj)max=lj;min=li;else max=li;min=lj;第20页，共103页。else int m=(i+j)/2;MaxMin(i,m,max,min);MaxMin(m+1,j,max1,min1);if(maxmin1)min=min1;第21页，共103页。设有设有n个元素的表，假定个元

9、素的表，假定n是是2的幂，即的幂，即n=2k，k是是正整数，程序正整数，程序55在最好、平均和最坏情况下的比较次在最好、平均和最坏情况下的比较次数都为数都为3n/22。2n 2)2/n(T)2/n(T2n 11n 0)n(T 第22页，共103页。第23页，共103页。第24页，共103页。在有序表（已按关键字值非减排序）中搜索给在有序表（已按关键字值非减排序）中搜索给定元素的问题。定元素的问题。第25页，共103页。在范围为在范围为left,right的表中搜索与的表中搜索与x有相同关有相同关键字值的元素；如果存在该元素，则函数返回该元素在键字值的元素；如果存在该元素，则函数返回该元素在表中

10、的位置，否则函数返回表中的位置，否则函数返回1，表示搜索失败。，表示搜索失败。第26页，共103页。二分搜索的基本思想是：首先将待查值二分搜索的基本思想是：首先将待查值x与有序表与有序表l0到到ln-1的中的下标为的中的下标为mid上的上的元素进行比较，若相等，则查找成功；否则，元素进行比较，若相等，则查找成功；否则，若若xlmid，则在，则在lmid+1到到ln-1中继续中继续查找。查找。第27页，共103页。每通过一次关键字的比较，搜索区间的长度每通过一次关键字的比较，搜索区间的长度就缩小一次，如此不断进行下去，直到找到就缩小一次，如此不断进行下去，直到找到值等于值等于x的元素；的元素；若

11、当前的查找区间为空若当前的查找区间为空,表示查找失败。表示查找失败。从上述查找思想可知，每进行一次关键字比从上述查找思想可知，每进行一次关键字比较，都将原区间一分为二，故称为二分搜索。较，都将原区间一分为二，故称为二分搜索。如果把要搜索区间的长度缩小一半，就称为如果把要搜索区间的长度缩小一半，就称为对半搜索。对半搜索。第28页，共103页。template int SortableList:BSearch(const T&x,int left,int right)const if (left=right)int m=Divide(left+right);if(xlm)return BSearc

12、h(x,m+1,right);else return m;return-1;第29页，共103页。对半搜索是一种二分搜索。设当前搜索的子表对半搜索是一种二分搜索。设当前搜索的子表 为（为（aleft,aleft+1,aright），），令令 m=(left+right)/2 第30页，共103页。例如，假设给定有序表中关键字为例如，假设给定有序表中关键字为8,17,25,44,68,77,98,100,115,125，将查找，将查找K=17和和K=120的的情况描述为以下形式。情况描述为以下形式。8 17 25 44 68 77 98 10 115 125 low high (a)初始情形 8

13、 17 25 44 68 44 98 100 115 125 low high mid (b)经过一次比较后的情形 第31页，共103页。8 17 25 44 68 77 98 100 115 125(c)经过二次比较后的情形 (Rmid.key=17)low mid high 查找 K=17 的示意图(查找成功)8 17 25 44 68 77 98 100 115 125 (a)初始情形 low high 第32页，共103页。8 17 25 44 68 77 98 100 115 125 (b)经过一次比较后的情形 mid low high 8 17 25 44 68 77 98 100

14、 115 125 (c)经过二次比较后的情形 mid low high 第33页，共103页。8 17 25 44 68 77 98 100 115 125 (d)经过三次比较后的情形 mid low high 17 25 44 77 98 100 115 125 high low mid (e)经过四次比较后的情形(highlow)查找 K=120 的示意图 (查找不成功)第34页，共103页。template int SortableList:BSearch(const T&x,int left,int right)const if (left=right)int m=(left+righ

15、t)/2;if(xlm)return BSearch(x,m+1,right);else return m;return-1;第35页，共103页。为了分析二分查找的性能，可以用二叉树来描述二分查找过程。把为了分析二分查找的性能，可以用二叉树来描述二分查找过程。把当前查找区间的中点作为根结点，左子区间和右子区间分别作为根的左当前查找区间的中点作为根结点，左子区间和右子区间分别作为根的左子树和右子树，左子区间和右子区间再按类似的方法，由此得到的二叉子树和右子树，左子区间和右子区间再按类似的方法，由此得到的二叉树 称 为 二 分 查 找 的 判 定 树。例 如，对 关 键 字 序 列树 称 为 二

16、 分 查 找 的 判 定 树。例 如，对 关 键 字 序 列8,17,25,44,68,77,98,100,115,125，的判定树下图。，的判定树下图。4 4 8 2 5 1 7 9 8 7 7 6 8 1 0 0 11 5 1 2 5 图 具 有 1 0 个 关 键 字 序 列 的 二 分 查 找 判 定 树 第36页，共103页。44 8 25 17 98 77 68 100 115 125 图 具 有 10 个 关 键 字 序 列 的 二 分 查 找 判 定 树 第37页，共103页。从上图可知，查找根结点从上图可知，查找根结点68，需一次查找，查找，需一次查找，查找17和和100，各

17、需二次查找，查找各需二次查找，查找8、25、77、115各需三次查找，查各需三次查找，查找找44、98、125各需四次查找。于是，可以得到结论：二各需四次查找。于是，可以得到结论：二叉树第叉树第K层结点的查找次数各为层结点的查找次数各为k次次(根结点为第根结点为第1层层)，而，而第第k层结点数最多为层结点数最多为2k-1个。假设该二叉树的深度为个。假设该二叉树的深度为h，则二分查找的成功的平均查找次数为（假设每个结点的则二分查找的成功的平均查找次数为（假设每个结点的查找概率相等）：查找概率相等）：第38页，共103页。ASL=1/n1/n 1/n(1+2 2+3 22+h 2h-1)=1/nn

18、iiicp1niic1hkkk112设设s=20+221+322+(h-1)2h-2+h2h-1则则2s=21+222+(h-2)2h-2+(h-1)2h-1+h2hs=2s-s=h.2h-(20+21+22+2h-2+2h-1)=h.2h-(2h-1)hkkk112第39页，共103页。ASL=1/n(log2(n+1)(2h-1+1)-n)=1/n(log2(n+1)(n+1)-n)=(n+1)/n log2(n+1)-1 =(1+1/n)log2(n+1)-1当当n很大时，很大时，ASL log2(n+1)-1 可以作为二分查找成功时的平可以作为二分查找成功时的平均查找长度，它的时间复杂

19、度为均查找长度，它的时间复杂度为 (log2n)。根据二叉树的性质，最大的结点数根据二叉树的性质，最大的结点数n=2n=2h h-1-1，h=logh=log2 2(n+1)(n+1)，于是可以得到平均查找次数于是可以得到平均查找次数ASL=s/nASL=s/nASL=1/n(h2ASL=1/n(h2h h-(2-(2h h-1)-1)第40页，共103页。在一个有在一个有n个元素的集合中，通过关键字值之间的比个元素的集合中，通过关键字值之间的比较，搜索指定关键字值的元素，任意这样的算法在最坏较，搜索指定关键字值的元素，任意这样的算法在最坏情况下至少需要作情况下至少需要作 log n+1次比较

20、。次比较。第41页，共103页。第42页，共103页。排序是将一个元素序列调整为按指定关键字值的递增排序是将一个元素序列调整为按指定关键字值的递增（或递减）次序排列的有序序列。（或递减）次序排列的有序序列。第43页，共103页。合并算法排序也属于分治方法。合并（合并算法排序也属于分治方法。合并（MergeMerge）就是将）就是将两个或多个有序表合并成一个有序表，例如下图所示的两两个或多个有序表合并成一个有序表，例如下图所示的两个有序表经合并运算后得到一个有序表。我们在此只用到个有序表经合并运算后得到一个有序表。我们在此只用到两个有序表的合并，称为二路合并两个有序表的合并，称为二路合并Two-

21、way mergeTwo-way merge）。）。A 7 10 13 15 B 4 8 19 20 C 4 7 8 10 13 15 19 20 第44页，共103页。合并排序（合并排序（Merge sortMerge sort）就是利用这种合并）就是利用这种合并过程进行排序，即先将过程进行排序，即先将n n个数据看成个数据看成n n个长度为个长度为l l的的表，将相邻的表成对合并，得到长度为表，将相邻的表成对合并，得到长度为2 2的的n/2n/2个有序表；个有序表；进一步再将相邻表成对合并，得到长度为进一步再将相邻表成对合并，得到长度为4 4的的n/4n/4个有序个有序表；表；如此重复做下

22、去，直至所有数据均合并；如此重复做下去，直至所有数据均合并到一个长度为到一个长度为n n的有序表为止，即完成排序。上述的有序表为止，即完成排序。上述每一次的合并过程称为一趟每一次的合并过程称为一趟PassPass），整个排序），整个排序过程叫二路合并排序。下图是二路合并排序过程过程叫二路合并排序。下图是二路合并排序过程的一个例子。的一个例子。第45页，共103页。7 15 13 10 4 20 19 87 15 10 13 4 20 8 197 15 13 10 4 20 19 8 7 10 13 15 4 8 19 20 4 7 8 10 13 15 19 20第46页，共103页。第47页

23、，共103页。template void SortableList:Merge(int left,int mid,int right)T*temp=new Tright-left+1;int i=left,j=mid+1,k=0;while(i=mid)&(j=right)if(li=lj)tempk+=li+;else tempk+=lj+;while(i=mid)tempk+=li+;while(j=right)tempk+=lj+;for(i=0,k=left;k=right;)lk+=tempi+;第48页，共103页。将待排序的元素序列一分为二分，得到两个长度基将待排序的元素序列一分

24、为二分，得到两个长度基本相等的子序列，如同对半搜索的做法；然后对两个本相等的子序列，如同对半搜索的做法；然后对两个子序列分别排序，如果子序列较长，还可继续细分，子序列分别排序，如果子序列较长，还可继续细分，直到子序列的长度不超过直到子序列的长度不超过1 1为止；当分解所得的子序为止；当分解所得的子序列已排列有序，可以采用上面介绍的将两个有序子序列已排列有序，可以采用上面介绍的将两个有序子序列，合并成一个有序子序列的方法，实现将子问题的列，合并成一个有序子序列的方法，实现将子问题的解组合成原问题解，这是分治法不可缺少的一步。解组合成原问题解，这是分治法不可缺少的一步。第49页，共103页。对于二

25、路合并，如果数据个数对于二路合并，如果数据个数n n是是2 2的整数次方，则的整数次方，则所需的趟数为所需的趟数为lognlogn，例如，例如n=8n=8，logn=3logn=3，故共需三趟合，故共需三趟合并过程。如果并过程。如果n n不是不是2 2的整数次方，则在每趟合并时表的的整数次方，则在每趟合并时表的数目不一定总是偶数个。若表的数目为奇数，就剩下一数目不一定总是偶数个。若表的数目为奇数，就剩下一个表要个表要“轮空轮空”，直接进入下一趟。这样，下一趟，直接进入下一趟。这样，下一趟合并时此表的长度与其它的表将不相同，因此我们合并时此表的长度与其它的表将不相同，因此我们设计的合并过程，并不

26、要求待合并的两个表长度必设计的合并过程，并不要求待合并的两个表长度必须相同。须相同。第50页，共103页。第51页，共103页。第52页，共103页。1n cn)2/n(T21n d)n(T 1n )2/(21n )(cnnTdnT设设a,b,c和和k为常数，为常数，T(n)=aT(n/b)+cnk，T(1)=c，则，则，kkkkkalogba )n(ba )nlogn(ba )n()n(Tb如如果果如如果果如如果果 第53页，共103页。使用使用可以形象地看到递推式的迭代过程。可以形象地看到递推式的迭代过程。T(n)=2T(n/2)+n的递归树的递归树第54页，共103页。快速排序采用一种特

27、殊的分划操作对排序问题进行分快速排序采用一种特殊的分划操作对排序问题进行分解，其分解方法是：在待排序的序列解，其分解方法是：在待排序的序列(K0,K1,Kn-1)中中选择一个元素作为分选择一个元素作为分划元素划元素，也称为，也称为主元主元（pivot）。）。不妨假定选择不妨假定选择K 为主元。经过一趟特殊的分划处理将原为主元。经过一趟特殊的分划处理将原序列中的元素序列中的元素重新排列重新排列，使得以主元为轴心，将序列分成，使得以主元为轴心，将序列分成左右两个子序列。主元左测子序列中所有元素都不大于主元，左右两个子序列。主元左测子序列中所有元素都不大于主元，主元右测子序列中所有元素都不小于主元。

28、主元右测子序列中所有元素都不小于主元。15 7 13 10 4 20 19 8 8 7 13 10 4 15 19 20第55页，共103页。1、主元最后的位置就是它最终的合适位置，进一步、主元最后的位置就是它最终的合适位置，进一步的运算过程中此数据即不必再动；的运算过程中此数据即不必再动；2、以后的排序运算只需在划分成的两部分里进行，、以后的排序运算只需在划分成的两部分里进行，两部分之间不会再有数据互换。两部分之间不会再有数据互换。3、第一次划分以后，再用相同的算法对划成的部分进行类、第一次划分以后，再用相同的算法对划成的部分进行类似的运算，即从每部分中任选一个数据将其划分成更小的两似的运算

29、，即从每部分中任选一个数据将其划分成更小的两部分，依此递归地做下去，直至每个小部分中的数据个数均部分，依此递归地做下去，直至每个小部分中的数据个数均不超过一个为止，排序过程即结束。不超过一个为止，排序过程即结束。15 7 13 10 4 20 19 8 8 7 13 10 4 15 19 20第56页，共103页。第57页，共103页。template int SortableList:Partition(int left,int right)/前置条件：前置条件：left right int i=left,j=right+1;do do i+;while(lilleft);if(ij)Swa

30、p(i,j);while(ij);Swap(left,j);return j;第58页，共103页。第59页，共103页。template void SortableList:QuickSort()QuickSort(0,n-1);template void SortableList:QuickSort(int left,int right)if(leftright)int j=Partition(left,right);QuickSort(left,j-1);QuickSort(j+1,right);第60页，共103页。若快速排序出现最坏的情形（每次能划分成两个子区间，若快速排序出现最坏的

31、情形（每次能划分成两个子区间，但其中一个是空），因此，快速排序的最坏时间复杂度为但其中一个是空），因此，快速排序的最坏时间复杂度为O(n2)。快速排序所占用的辅助空间为栈的深度，故最好的空间复杂度为快速排序所占用的辅助空间为栈的深度，故最好的空间复杂度为O（logn），最坏的空间复杂度为），最坏的空间复杂度为O(n2)。若快速排序出现最好的情形（左、右子区间的长度大致相等），快若快速排序出现最好的情形（左、右子区间的长度大致相等），快速排序的最好时间复杂度应为速排序的最好时间复杂度应为O（nlog2n）。）。理论上已经证明，快速排序的平均时间复杂度也为理论上已经证明，快速排序的平均时间复杂度也

32、为O O（nlognnlogn）。）。第61页，共103页。)k(An21n )1kn(A)k(A(n11n)n(A1n0k1n0k )k(A2)1n(n)n(nA1n0k )k(A2)1n(n)1n(A1n2n0k ）（第62页，共103页。)1n(log2xdx2k12 321n2n21n221A 1n2n21n22n3nA n21n21n2nA 1n2n1nA 1n)n(A 1n3k1n 2 e ）（）（）（）（)nlogn(O)1n(log)1n(2)n(Ae 第63页，共103页。任何一个通过关键字值比较对任何一个通过关键字值比较对n个元素进行排序的算个元素进行排序的算法，在最坏情况

33、下，至少需作（法，在最坏情况下，至少需作（n/4）log n次比较。次比较。第64页，共103页。第65页，共103页。第66页，共103页。第67页，共103页。设原表长度为设原表长度为n，假定经过一趟分划，分成两个左右，假定经过一趟分划，分成两个左右子表，其中左子表是主元及其左边元素的子表，设其长子表，其中左子表是主元及其左边元素的子表，设其长度为度为p，右子表是主元右边元素的子表。那么，若，右子表是主元右边元素的子表。那么，若k=p，则主元就是第则主元就是第k小元素；否则若小元素；否则若kp，则第，则第k小元素必定在右子表中，需求解的小元素必定在右子表中，需求解的子问题成为在右子表中求第

34、子问题成为在右子表中求第k-p小元素。小元素。15 7 13 10 4 20 19 8 8 7 13 10 4 15 19 20第68页，共103页。假定表中元素各不相同，并且随机选择主元，即在下假定表中元素各不相同，并且随机选择主元，即在下标区间标区间left,right中随机选择一个下标中随机选择一个下标r，以该下标处的，以该下标处的元素为主元。元素为主元。第69页，共103页。template ResultCode SortableList:Select1(T&x,int k)if(nn|k=0)return OutOfBounds;int left=0,right=n;ln=INFTY

35、;do int j=rand()%(right-left+1)+left;Swap(left,j);j=Partition(left,right);if(k=j+1)x=lj;return Success;else if(kj+1)right=j;else left=j+1;while(true);第70页，共103页。程序程序513的的Select算法的平均时间算法的平均时间A(n)=O(n)。算法的最坏情况时间复杂度算法的最坏情况时间复杂度O(n2)。第71页，共103页。改进的选择算法采用改进的选择算法采用(median of(median of medians rule)medians

36、 rule)确定主元确定主元 第72页，共103页。第73页，共103页。ResultCode SortableList:Select(T&x,int k)if(nn|k=0)return OutOfBounds;int j=Select(k,0,n-1,5);x=lj;return Success;第74页，共103页。template int SortableList:Select(int k,int left,int right,int r)int n=right-left+1;if(n=r)InsertSort(left,right);return left+k-1;第75页，共103

37、页。for(int i=1;i=n/r;i+)InsertSort(left+(i-1)*r,left+i*r-1);Swap(left+i-1,left+(i-1)*r+Ceil(r,2)-1);int j=Select(Ceil(n/r,2),left,left+(n/r)-1,r);Swap(left,j);j=Partition(left,right);if(k=j-left+1)return j;else if(kj-left+1)return Select(k,left,j-1,r);else return Select(k-(j-left+1),j+1,right,r);第76页

38、，共103页。以二次取中的中间值以二次取中的中间值mm为主元，经过一趟分划，左、为主元，经过一趟分划，左、右两个子表的大小均至多为：右两个子表的大小均至多为：设设T(n)为当表长为为当表长为n时执行程序时执行程序514所需的时间。所需的时间。T(n)由三部分时间组成：由三部分时间组成：第77页，共103页。由于允许包含相同元素，左子表中除了小于由于允许包含相同元素，左子表中除了小于mm的元素的元素外，还包含与外，还包含与mm相同值的元素。因此，左子表的大小至相同值的元素。因此，左子表的大小至多可达多可达 容易用归纳法证明对于所有容易用归纳法证明对于所有n 90，第78页，共103页。第79页，

39、共103页。矩阵相乘矩阵相乘第80页，共103页。矩阵乘积的矩阵乘积的StrassenStrassen算法算法 C=AB=(cij)nn。nkkjikijnjibac1,2,1,求求C=ABC=AB即对即对n n2 2个元素个元素c cijij进行计算，故要作进行计算，故要作n n3 3次乘法。相当次乘法。相当时间内没有人怀疑过是否可以用少于时间内没有人怀疑过是否可以用少于n n3 3次乘法来完成。其实次乘法来完成。其实不然，先以不然，先以n=2n=2的矩阵乘积为例。的矩阵乘积为例。对于矩阵对于矩阵2221121122211211,bbbbBaaaaA第81页，共103页。则有：则有：2221

40、121122211211bbbbaaaaABC22221221212211212212121121121111babababababababa22211211cccc共需作共需作8次乘法和次乘法和4次加法。次加法。第82页，共103页。C11A11B11+A12B21C12A11B12+A12B22 C21A21B11+A22B21 C22A21B12+A22B22 222112112221121122211211CCCCBBBBAAAA第83页，共103页。C11A11B11+A12B21C12A11B12+A12B22 C21A21B11+A22B21 C22A21B12+A22B22 2

41、n dn)2/n(T82n b)n(T2 T(n)=(n3)第84页，共103页。设设a,b,c和和k为常数，为常数，T(n)=aT(n/b)+cnk，T(1)=c，则，则，kkkkkalogba )n(ba )nlogn(ba )n()n(Tb如果如果如果如果如果如果 第85页，共103页。P=(A11+A22)(B11+B22)Q=(A21+A22)B11R=A11(B12-B22)S=A21(B21-B11)T=(A11+A12)B22U=(A21-A11)(B11+B12)V=(A12-A22)(B21+B22)第86页，共103页。C11=P+S-T+VC12=R+TC21=Q+SC

42、22=P+R-Q+U 2n dn)2/n(T72n b)n(T2 第87页，共103页。第88页，共103页。我们研究两个我们研究两个n位二进制数相乘的问题。用普通的方法运算，位二进制数相乘的问题。用普通的方法运算，将乘数的每一位（由低位至高位）逐个去乘被乘数，每乘一将乘数的每一位（由低位至高位）逐个去乘被乘数，每乘一次将乘积与原来的积相加，然后乘数和乘积移位一步，如此次将乘积与原来的积相加，然后乘数和乘积移位一步，如此下去直至乘数的最高位运算完即得出结果，这样运算共需下去直至乘数的最高位运算完即得出结果，这样运算共需n2 次一位乘一位运算，次一位乘一位运算，n(n-1)次一位加一位运算和次一

43、位加一位运算和n次移位，次移位，假设两个一位数相乘，两个一位数相加和任何数移位一步假设两个一位数相乘，两个一位数相加和任何数移位一步所需运算时间均为所需运算时间均为O(1)，即均为常数。总运算复杂性为，即均为常数。总运算复杂性为O（n2）。）。第89页，共103页。第90页，共103页。现在用分治法来做。设现在用分治法来做。设n=2r,将两个数都按位数划分成两段，将两个数都按位数划分成两段，如图所示，如图所示，第91页，共103页。因 dcybaxnn2222则 bdbcadcayxnn22)(2这需要三次这需要三次n位的加法，一次位的加法，一次n步移位，一次步移位，一次n/2步移位和步移位和

44、四次四次n/2位的乘法。位的乘法。第92页，共103页。设用分治法做两个设用分治法做两个n位数乘法的复杂性为位数乘法的复杂性为T（n），因加法和移位都是），因加法和移位都是O（n），故：），故：第93页，共103页。这样并没有显出其优越性，我们可以将其进一步改这样并没有显出其优越性，我们可以将其进一步改进，增加一些加法运算以减少乘法运算。进，增加一些加法运算以减少乘法运算。设设a,b,c和和k为常数，为常数，T(n)=aT(n/b)+cnk，T(1)=c，则，则，kkkkkalogba )n(ba )nlogn(ba )n()n(Tb如如果果如如果果如如果果 第94页，共103页。由于 bdb

45、cadcayxnn22)(2令 )(,dcbawbdvacu 则 vuwbcad)(减少了乘法运算的次数。减少了乘法运算的次数。因 dcybaxnn2222则 bdbcadcayxnn22)(2第95页，共103页。KTn KnnTnT)1()1()2(3)(为解此递归方程，将问题的逐层划分列表如下：问题的个数13323r-23r-12r问题的大小2r2r-12r-22221每个问题的运算时间K2rK2r-1K2r-2K22K2K第96页，共103页。显然较普通方法更有效。这种思想同样可以用于十显然较普通方法更有效。这种思想同样可以用于十进制数的乘法中。进制数的乘法中。类似于上述例子，可以看出

46、，一般情况下采用分治解决类似于上述例子，可以看出，一般情况下采用分治解决法划分子问题时，使各子问题的规模尽量相等为好。此外，法划分子问题时，使各子问题的规模尽量相等为好。此外，如果是逐层划分，采用递归形式可以使程序简而明，分析起如果是逐层划分，采用递归形式可以使程序简而明，分析起来也较为方便。来也较为方便。计算：计算：23483825=？第97页，共103页。循环赛日程表循环赛日程表 设有设有n=2n=2k k个运动员要进行网球循环赛。现要设计一个个运动员要进行网球循环赛。现要设计一个满足以下要求的比赛日程表：满足以下要求的比赛日程表：（1 1）每个选手必须与其他）每个选手必须与其他n-1n-

47、1个选手各赛一次；个选手各赛一次；（2 2）每个选手一天只能赛一次；）每个选手一天只能赛一次；（3 3）循环赛一共进行）循环赛一共进行n-1n-1天。天。按此要求可将比赛日程表设计成有按此要求可将比赛日程表设计成有n n行和行和n n列的一个表。列的一个表。在表中第在表中第i i行和第行和第j j列处填入第列处填入第i i个选手在第个选手在第j j天所遇到的选手。天所遇到的选手。第98页，共103页。4个选手的比赛日程表第99页，共103页。第100页，共103页。按分治策略，我们可以将所有选手对分为两组，按分治策略，我们可以将所有选手对分为两组，n n个选手的比赛个选手的比赛日程表就可以通过

48、为日程表就可以通过为n/2n/2个选手设计的比赛日程表来决定。递归地用个选手设计的比赛日程表来决定。递归地用这种一分为二的策略对选手进行分割，直到只剩下这种一分为二的策略对选手进行分割，直到只剩下2 2个选手时，比赛个选手时，比赛日程表的制定就变得很简单。这时只要让这日程表的制定就变得很简单。这时只要让这2 2个选手进行比赛就可以个选手进行比赛就可以了。了。下图所列出的正方形表是下图所列出的正方形表是4个选手的比赛日程表。其中左上角与个选手的比赛日程表。其中左上角与左下角的两小块分别为选手左下角的两小块分别为选手1至选手至选手2和选手和选手3至选手至选手4第第1天的比赛日天的比赛日程。据此，将

49、左上角小块中的所有数字按其相对位置抄到右下角，程。据此，将左上角小块中的所有数字按其相对位置抄到右下角，将左下角小块中的所有数字按其相对位置抄到右上角，这样我们就将左下角小块中的所有数字按其相对位置抄到右上角，这样我们就分别安排好了选手分别安排好了选手1至选手至选手2和选手和选手3至选手至选手4在后在后2天的比赛日程。这天的比赛日程。这种安排是符合要求的。种安排是符合要求的。第101页，共103页。4个选手的比赛日程表第102页，共103页。依此思想容易将这个比赛日程表推广到具有任意多个依此思想容易将这个比赛日程表推广到具有任意多个选手的情形。下表是选手的情形。下表是8个选手的日程安排表。个选手的日程安排表。12342 3 41 4 34 1 23 2 15 6 7 86 5 8 77 8 5 68 7 6 556786 7 85 8 78 5 67 6 51 2 3 42 1 4 33 4 1 24 3 2 1第103页，共103页。