《理学《算法设计与分析》第章》由会员分享，可在线阅读，更多相关《理学《算法设计与分析》第章（103页珍藏版）》请在金锄头文库上搜索。
1、算法设计与分析算法设计与分析DeSign and Analysis of AlgorithmsIn C+“十一五十一五”国家级规划教国家级规划教材材 陈慧南陈慧南陈慧南陈慧南 编著编著编著编著电子工业出版社电子工业出版社电子工业出版社电子工业出版社第第2部分部分算法设计策略算法设计策略第第5章章分治法分治法 5.15.1 分治法的基本思想分治法的基本思想分治法的基本思想分治法的基本思想 5.25.2 求最大最小元求最大最小元求最大最小元求最大最小元 5.35.3 二分搜索二分搜索二分搜索二分搜索 5.45.4 排序问题排序问题排序问题排序问题5.55.5选择问题选择问题选择问题选择问题5.65
2、.6斯特拉森矩阵乘法斯特拉森矩阵乘法斯特拉森矩阵乘法斯特拉森矩阵乘法5.1一般方法一般方法5.1.1分治法的基本思想分治法的基本思想分分分分治治治治法法法法顾顾名名思思义义就就是是分分而而治治之之。一一个个问问题题能能够够用用分分治治法法求求解解的的要要素素是是：第第一一，问问题题能能够够按按照照某某种种方方式式分分解解成成若若干干个个规规模模较较小小、相相互互独独立立且且与与原原问问题题类类型型相相同同的的子子问问题题；第第二二，子子问问题题足足够够小小时时可可以以直直接接求求解解；第第三三，能能够够将将子子问问题题的的解解组组合合成成原问题的解。原问题的解。由由于于分分治治法法要要求求分分
3、解解成成同同类类子子问问题题，并并允允许许不不断断分分解解，使使问问题题规规模模逐逐步步减减小小，最最终终可可用用已已知知的的方方法法求求解解足足够够小小的的问问题题，因因此此，分分治治法法求求解解很很自自然导致一个递归算法。然导致一个递归算法。【程序程序程序程序5-15-1】分治法分治法SolutionTypeDandC(ProblemTypeP)ProblemTypeP1，P2，Pk;if(Small(P)returnS(P);elseDivide(P， P1， P2， ， Pk);ReturnCombine(DandC(P1)，DandC(P2)，DandC(Pk);【程序程序程序程序5
4、-25-2】一分为二的分治法一分为二的分治法SolutionTypeDandC(intleft，intright)if(Small(left,right)returnS(left,right);elseintm=Divide(left，right);ReturnCombine(DandC(left，m)，DandC(m+1，right);5.1.2算法分析算法分析采用分治法求解问题通常得到一个递归算法。如采用分治法求解问题通常得到一个递归算法。如果较大的问题被分解成同样大小的几部分，那么分果较大的问题被分解成同样大小的几部分，那么分析相应算法的执行时间，往往可得到如下的递推关析相应算法的执行时
5、间，往往可得到如下的递推关系式：系式：T(n)=aT(n/b)+cnk，T(1)=c定理定理定理定理5-15-1设设a,b,c和和k为常数，为常数，T(n)=aT(n/b)+cnk，T(1)=c，则，则，设设r=bk/a，下面分三种情况计算下面分三种情况计算。（1）若）若r1，则则所以所以例如：例如：(1)(1)T(nT(n)=2T(n/2)+n)=2T(n/2)+na=2,b=2,k=1,a=a=2,b=2,k=1,a=b bk k所以所以所以所以 T(nT(n)=)= ( (nlog(nnlog(n) )(2)(2)T(nT(n)=4T(n/4)+n)=4T(n/4)+n2 2a=4,b=
6、4,k=2,aa=4,b=4,k=2,aa=16,b=2,k=2,ab bk k所以所以所以所以 T(nT(n)=)= (n(n4 4) )5.1.3数据结构数据结构 【程序程序程序程序5 53 3】 可排序表类可排序表类可排序表类可排序表类templatestructE/可排序表中元素的类型可排序表中元素的类型operatorK()constreturnkey;/重载类型转换运算符重载类型转换运算符Kkey;/关键字可以比较大小关键字可以比较大小Ddata;/其他数据其他数据; templateclassSortableList/可排序表类可排序表类public:SortableList(i
7、ntmSize)/构造函数构造函数maxSize=mSize;l=newTmaxSize;n=0;SortableList()deletel; /析构函数析构函数 private: T*l; /定义动态一维数组定义动态一维数组intmaxSize; /线性表的最大表长线性表的最大表长intn; /线性表的实际长度线性表的实际长度; 5.2求最大最小元求最大最小元问题问题在一个元素集合中寻找最大元素和最小元在一个元素集合中寻找最大元素和最小元素的问题。素的问题。5.2.1分治法求解分治法求解【程序程序程序程序5 54 4】 求最大最小元求最大最小元求最大最小元求最大最小元templatevoid
8、SortableList:MaxMin(T&max,T&min)constif(n=0)return;max=min=l0;for(inti=1;imax)max=li;if(limin)min=li;/TnTn=2(n-1) =2(n-1) 5.2.1分治法求解分治法求解【程序程序程序程序5 54 4】 求最大最小元求最大最小元求最大最小元求最大最小元templatevoidSortableList:MaxMin(T&max,T&min)constif(n=0)return;max=min=l0;for(inti=1;imax)max=li;elseif(limin)min=li;WnWn=
9、2(n-1) =2(n-1) ( ( ( (递减有序）递减有序）递减有序）递减有序） BnBn=n-1=n-1( ( ( (递增有序）递增有序）递增有序）递增有序）【程序程序程序程序5 55 5】分治法求最大最小元分治法求最大最小元分治法求最大最小元分治法求最大最小元templatevoidSortableList:MaxMin(inti,intj,T&max,T&min)constTmin1,max1;if(i=j)max=min=li;elseif(i=j-1)if(lilj)max=lj;min=li;elsemax=li;min=lj;elseintm=(i+j)/2;MaxMin(i
10、,m,max,min);MaxMin(m+1,j,max1,min1);if(maxmin1)min=min1;5.2.2时间分析时间分析定理定理52设设有有n个个元元素素的的表表，假假定定n是是2的的幂幂，即即n=2k，k是是正正整整数数，程程序序55在在最最好好、平平均均和和最最坏坏情情况况下下的比较次数都为的比较次数都为3n/22。n=2n=2k k,T(n)=2T(n/2)+2,T(n)=2T(n/2)+2T(nT(n)=3n/2-2)=3n/2-25.3二分搜索二分搜索问题问题在在有有序序表表（已已按按关关键键字字值值非非减减排排序序）中中搜索给定元素的问题。搜索给定元素的问题。5.
11、3.1分治法求解分治法求解intint SortableListSortableList:BSearch(constBSearch(constT&x,T&x,intint left,intleft,intright)constright)const后置条件后置条件后置条件后置条件: :在范围为在范围为left,right的表中搜索与的表中搜索与x有有相同关键字值的元素；如果存在该元素，则函数返相同关键字值的元素；如果存在该元素，则函数返回该元素在表中的位置，否则函数返回回该元素在表中的位置，否则函数返回1，表示搜，表示搜索失败。索失败。二分搜索二分搜索1.二分二分搜索搜索的基本思想的基本思想二
12、分搜索的基本思想是：首先将待查二分搜索的基本思想是：首先将待查值值x与有序表与有序表l0到到ln-1的中的下标为的中的下标为mid上的元素进行比较，若相等，则查上的元素进行比较，若相等，则查找成功；否则，若找成功；否则，若xlmid，则，则在在lmid+1到到ln-1中继续查找。中继续查找。每通过一次关键字的比较，搜索区间的长度每通过一次关键字的比较，搜索区间的长度就缩小一次，如此不断进行下去，直到找到就缩小一次，如此不断进行下去，直到找到值等于值等于x的元素；的元素；若当前的查找区间为空若当前的查找区间为空,表示查找失败。表示查找失败。从上述查找思想可知，每进行一次关键字比从上述查找思想可知
13、，每进行一次关键字比较，都将原区间一分为二，故称为二分搜索。较，都将原区间一分为二，故称为二分搜索。如果把要搜索区间的长度缩小一半，就称为如果把要搜索区间的长度缩小一半，就称为对半搜索。对半搜索。【程序程序程序程序5 56 6】二分搜索算法框架二分搜索算法框架二分搜索算法框架二分搜索算法框架templateintSortableList:BSearch(constT&x,intleft,intright)constif(left=right)intm=Divide(left+right);if(xlm)returnBSearch(x,m+1,right);elsereturnm;return-
14、1;5.3.2对半搜索对半搜索 对对对对半搜索半搜索半搜索半搜索对半搜索是一种二分搜索。设当前搜索的子表对半搜索是一种二分搜索。设当前搜索的子表为（为（aleft,aleft+1,aright），），令令m=(left+right)/2 例如，假设给定有序表中关键字为例如，假设给定有序表中关键字为8,17,25,44,68,77,98,100,115,125，将查找，将查找K=17和和K=120的情况描述为以下形式。的情况描述为以下形式。【程序程序程序程序5 57 7】 对对对对半搜索半搜索半搜索半搜索递归递归递归递归算法算法算法算法templateintSortableList:BSearc
15、h(constT&x,intleft,intright)constif(left=right)intm=(left+right)/2;if(xlm)returnBSearch(x,m+1,right);elsereturnm;return-1;二分二分二分二分查查查查找的性能分析找的性能分析找的性能分析找的性能分析为为了了分分析析二二分分查查找找的的性性能能，可可以以用用二二叉叉树树来来描描述述二二分分查查找找过过程程。把把当当前前查查找找区区间间的的中中点点作作为为根根结结点点，左左子子区区间间和和右右子子区区间间分分别别作作为为根根的的左左子子树树和和右右子子树树，左左子子区区间间和和右右
16、子子区区间间再再按按类类似似的的方方法法，由由此此得得到到的的二二叉叉树树称称为为二二分分查查找找的的判判定定树树。例例如如，对对关关键键字字序序列列8,17,25,44,68,77,98,100,115,125，的的判判定定树下图。树下图。二分二分二分二分查查查查找的性能分析找的性能分析找的性能分析找的性能分析查找成功：最好：查找成功：最好：查找成功：最好：查找成功：最好：Ws=1Ws=1Ws=1Ws=1；最坏：；最坏：；最坏：；最坏：Ws= Ws= Ws= Ws= lognlognlognlogn +1= +1= +1= +1= O(lognO(lognO(lognO(logn) ) )
17、)查找失败：查找失败：查找失败：查找失败：WfWfWfWf= = = = lognlognlognlogn +1 = +1 = +1 = +1 = ( ( ( (lognlognlognlogn) ) ) )搜索成功的平均搜索成功的平均搜索成功的平均搜索成功的平均时间时间时间时间复复复复杂杂杂杂度：度：度：度：从从上上图图可可知知，查查找找根根结结点点68，需需一一次次查查找找，查查找找17和和100，各各需需二二次次查查找找，查查找找8、25、77、115各各需需三三次次查查找找，查查找找44、98、125各各需需四四次次查查找找。于于是是，可可以以得得到到结结论论：二二叉叉树树第第K层层结
18、结点点的的查查找找次次数数各各为为k次次(根根结结点点为为第第1层层)，而而第第k层层结结点点数数最最多多为为2k-1个个。假假设设该该二二叉叉树树的的深深度度为为h，则则二二分分查查找找的的成成功功的的平平均均查查找次数为（假设每个结点的查找概率相等）：找次数为（假设每个结点的查找概率相等）：ASL=1/n1/n1/n(1+2 2+3 22+h 2h-1)=1/n设设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)ASL=1/n
19、(log2(n+1)(2h-1+1)-n)=1/n(log2(n+1)(n+1)-n)=(n+1)/nlog2(n+1)-1=(1+1/n)log2(n+1)-1当当n很大时，很大时，ASL log2(n+1)-1可以作为二分查找可以作为二分查找成功时的平均查找长度，它的时间复杂度为成功时的平均查找长度，它的时间复杂度为 (log2n)。根据二叉树的性质，最大的结点数根据二叉树的性质，最大的结点数n=2n=2h h-1-1，h=logh=log2 2(n+1) (n+1) ，于是可以得到平均查找次数，于是可以得到平均查找次数ASL=ASL=s/ns/nASL= 1/n(h2ASL= 1/n(h
20、2h h-(2-(2h h-1)-1)5.3.4搜索算法的时间下界搜索算法的时间下界 定理定理定理定理5 5 5 56 6 6 6 在在一一个个有有n个个元元素素的的集集合合中中，通通过过关关键键字字值值之之间间的的比比较较，搜搜索索指指定定关关键键字字值值的的元元素素，任任意意这这样样的的算算法法在最坏情况下至少需要作在最坏情况下至少需要作 logn +1次比较。次比较。5.4 排序问题排序问题 问题问题 排序是将一个元素序列调整为按指定关键字值的排序是将一个元素序列调整为按指定关键字值的递增（或递减）次序排列的有序序列。递增（或递减）次序排列的有序序列。合并两个有序表：合并两个有序表：合并
21、两个有序表：合并两个有序表：合并算法排序也属于分治方法。合并（合并算法排序也属于分治方法。合并（MergeMerge）就是将两个或多个有序表合并成一个有序表，例如就是将两个或多个有序表合并成一个有序表，例如下图所示的两个有序表经合并运算后得到一个有序下图所示的两个有序表经合并运算后得到一个有序表。我们在此只用到两个有序表的合并，称为二路表。我们在此只用到两个有序表的合并，称为二路合并合并Two-way mergeTwo-way merge）。）。5.4.1合并排序合并排序合并排序（合并排序（Merge sortMerge sort）就是利用这种合并就是利用这种合并过程进行排序，即先将过程进行排
22、序，即先将n n个数据看成个数据看成n n个长度为个长度为l l的表，将相邻的表成对合并，得到长度为的表，将相邻的表成对合并，得到长度为2 2的的n/2n/2个有序表；进一步再将相邻表成对合并，得个有序表；进一步再将相邻表成对合并，得到长度为到长度为4 4的的n/4n/4个有序表；个有序表；如此重复做；如此重复做下去，直至所有数据均合并到一个长度为下去，直至所有数据均合并到一个长度为n n的有的有序表为止，即完成排序。上述每一次的合并过序表为止，即完成排序。上述每一次的合并过程称为一趟程称为一趟PassPass），），整个排序过程叫二路合整个排序过程叫二路合并排序。下图是二路合并排序过程的一个
23、例子。并排序。下图是二路合并排序过程的一个例子。合并排序合并排序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合并两个有序序列合并两个有序序列【程序程序程序程序5 59 9】 合并两个有序序列（合并两个有序序列（合并两个有序序列（合并两个有序序列（MergeMerge函数）函数）函数）函数）templatevoidSortableList:Merge(intleft,intmid,intright)T*temp=newTright-lef
24、t+1;inti=left,j=mid+1,k=0;while(i=mid)&(j=right)if(li=lj)tempk+=li+;elsetempk+=lj+;while(i=mid)tempk+=li+;while(j=right)tempk+=lj+;for(i=0,k=left;k=right;)lk+=tempi+;分治法求解分治法求解 将将待待排排序序的的元元素素序序列列一一分分为为二二分分，得得到到两两个个长长度度基基本本相相等等的的子子序序列列，如如同同对对半半搜搜索索的的做做法法；然然后后对对两两个个子子序序列列分分别别排排序序，如如果果子子序序列列较较长长，还还可可继继
25、续续细细分分，直直到到子子序序列列的的长长度度不不超超过过1 1为为止止；当当分分解解所所得得的的子子序序列列已已排排列列有有序序，可可以以采采用用上上面面介介绍绍的的将将两两个个有有序序子子序序列列，合合并并成成一一个个有有序序子子序序列列的的方方法法，实实现现将将子子问问题题的的解解组组合合成成原原问问题题解解，这这是是分分治治法法不不可可缺缺少的一步。少的一步。 对于二路合并，如果数据个数对于二路合并，如果数据个数n n是是2 2的整数的整数次方，则所需的趟数为次方，则所需的趟数为lognlogn，例如例如n=8n=8，logn=3logn=3，故共需三趟合并过程。如果故共需三趟合并过程
26、。如果n n不是不是2 2的整数次的整数次方，则在每趟合并时表的数目不一定总是偶数方，则在每趟合并时表的数目不一定总是偶数个。若表的数目为奇数，就剩下一个表要个。若表的数目为奇数，就剩下一个表要“轮轮空空”，直接进入下一趟。这样，下一趟合并时，直接进入下一趟。这样，下一趟合并时此表的长度与其它的表将不相同，因此我们设此表的长度与其它的表将不相同，因此我们设计的合并过程，并不要求待合并的两个表长度计的合并过程，并不要求待合并的两个表长度必须相同。必须相同。 【程序程序程序程序5 5 5 510101010】两路两路两路两路合并排序合并排序合并排序合并排序templatetemplatevoidv
27、oidSortableListSortableList:MergeSort(intMergeSort(int left,intleft,intright)right) if(leftright)if(leftright)intintmid=(left+right)/2;mid=(left+right)/2;MergeSort(left,midMergeSort(left,mid););MergeSort(mid+1,right);MergeSort(mid+1,right);Merge(left,mid,right);Merge(left,mid,right); templatetemplat
28、evoidvoidSortableListSortableList:MergeSortMergeSort() () MergeSort(0,n-1);MergeSort(0,n-1); 性能分析性能分析合并排序递归算法的时间复杂度为合并排序递归算法的时间复杂度为合并排序递归算法的时间复杂度为合并排序递归算法的时间复杂度为 ( (nlognlog n)n)。定理定理定理定理5-15-1设设a,b,c和和k为常数，为常数，T(n)=aT(n/b)+cnk，T(1)=c，则，则，使用使用递归树递归树递归树递归树可以形象地看到递推式的迭代过程。可以形象地看到递推式的迭代过程。 例例例例2-132-13
29、 T(n)=2T(n/2)+n的递归树的递归树递归路径：递归路径：递归路径：递归路径：n-(1/2)n-(1/2)n-(1/2)n-(1/2)n-(1/2)n-(1/2)n-(1/2)n-(1/2)2 2 2 2n.(1/2)n.(1/2)n.(1/2)n.(1/2)k k k kn1n1n1n1(1/2)(1/2)(1/2)(1/2)k k k kn=1n=1n=1n=1，即，即，即，即n/2n/2n/2n/2k k k k=1=1=1=1，即，即，即，即2 2 2 2k k k k=n=n=n=n，k=logk=logk=logk=log2 2 2 2n=n=n=n=lognlognlog
30、nlogn所以所以所以所以 T(nT(nT(nT(n)=n*(logn+1)= )=n*(logn+1)= )=n*(logn+1)= )=n*(logn+1)= ( ( ( (nlognnlognnlognnlogn) ) ) )5.4.2快速排序快速排序快速排序采用一种特殊的分划操作对排序问题进快速排序采用一种特殊的分划操作对排序问题进行分解，其分解方法是：在待排序的序列行分解，其分解方法是：在待排序的序列(K0,K1,Kn-1)中选择一个元素作为分中选择一个元素作为分划元素划元素，也称，也称为为主元主元（pivot）。）。不妨假定不妨假定选择选择K 为为主元。主元。经过经过一一趟特殊的分
31、划趟特殊的分划处处理将原序列中的元素理将原序列中的元素重新排列重新排列，使，使得以主元得以主元为轴为轴心，将序列分成左右两个子序列。主心，将序列分成左右两个子序列。主元左元左测测子序列中所有元素都不大于主元，主元右子序列中所有元素都不大于主元，主元右测测子序列中所有元素都不小于主元。子序列中所有元素都不小于主元。15 7 13 10 4 20 19 8 8 7 13 10 4 15 19 201、主元最后的位置就是它最、主元最后的位置就是它最终终的合适位置，的合适位置，进进一步一步的运算的运算过过程中此数据即不必再程中此数据即不必再动动；2、以后的排序运算只需在划分成的两部分里、以后的排序运算
32、只需在划分成的两部分里进进行，行，两部分之两部分之间间不会再有数据互不会再有数据互换换。3、第一次划分以后，再用相同的算法、第一次划分以后，再用相同的算法对对划成的部分划成的部分进进行行类类似的运算，即从每部分中任似的运算，即从每部分中任选选一个数据将其一个数据将其划分成更小的两部分，依此划分成更小的两部分，依此递归递归地做下去，直至每地做下去，直至每个小部分中的数据个数均不超个小部分中的数据个数均不超过过一个一个为为止，排序止，排序过过程即程即结结束。束。15 7 13 10 4 20 19 8 8 7 13 10 4 15 19 20 分划操作分划操作【程序程序程序程序5 5 5 5111
33、11111】 分划函数分划函数分划函数分划函数templateintSortableList:Partition(intleft,intright)/前置条件：前置条件：left rightinti=left,j=right+1;dodoi+;while(lilleft);if(ij)Swap(i,j);while(ij);Swap(left,j);returnj;快速排序算法快速排序算法【程序程序程序程序5 5 5 512121212】快速排序快速排序快速排序快速排序 templatevoidSortableList:QuickSort()QuickSort(0,n-1);templatev
34、oidSortableList:QuickSort(intleft,intright)if(leftright)intj=Partition(left,right);QuickSort(left,j-1);QuickSort(j+1,right);若若快快速速排排序序出出现现最最坏坏的的情情形形（每每次次能能划划分分成成两两个个子子区区间间，但但其其中中一一个个是是空空），因因此此，快快速速排排序序的的最最坏坏时时间间复复杂杂度度为为O(n2)。快快速速排排序序所所占占用用的的辅辅助助空空间间为为栈栈的的深深度度，故故最最好好的的空空间间复杂度为复杂度为O（logn），），最坏的空间复杂度为最
35、坏的空间复杂度为O(n2)。若若快快速速排排序序出出现现最最好好的的情情形形（左左、右右子子区区间间的的长长度度大大致致相等），快速排序的最好时间复杂度应为相等），快速排序的最好时间复杂度应为O（nlog2n）。）。 时间分析时间分析理论上已经证明，快速排序的平均时间复杂度也为理论上已经证明，快速排序的平均时间复杂度也为O O（nlognnlogn）。）。平均情况时间平均情况时间平均情况时间平均情况时间 5.4.3排序算法的时间下界排序算法的时间下界定理定理57任任何何一一个个通通过过关关键键字字值值比比较较对对n个个元元素素进进行行排排序序的的算算法法，在在最最坏坏情情况况下下，至至少少需需
36、作作（n/4）logn次比次比较较。5.5选择问题选择问题 问题问题选择问题（选择问题（选择问题（选择问题（select problemselect problemselect problemselect problem）是指在是指在是指在是指在n n n n个元素的集个元素的集个元素的集个元素的集合中，选出某个元素值大小在集合中处于第合中，选出某个元素值大小在集合中处于第合中，选出某个元素值大小在集合中处于第合中，选出某个元素值大小在集合中处于第k k k k位的位的位的位的元素，即所谓的元素，即所谓的元素，即所谓的元素，即所谓的求第求第求第求第k k小元素问题小元素问题小元素问题小元素问题
37、( ( ( (kthkthkthkth-smallest)-smallest)-smallest)-smallest)。 5.5.1分治法求解分治法求解设设原原表表长长度度为为n，假假定定经经过过一一趟趟分分划划，分分成成两两个个左左右右子子表表，其其中中左左子子表表是是主主元元及及其其左左边边元元素素的的子子表表，设设其其长长度度为为p，右右子子表表是是主主元元右右边边元元素素的的子子表表。那那么么，若若k=p，则则主主元元就就是是第第k小小元元素素；否否则则若若kp，则则第第k小小元元素素必必定定在在右右子子表表中中，需需求求解解的的子子问问题题成成为为在在右右子子表表中中求求第第k-p小
38、元素。小元素。15 7 13 10 4 20 19 8 8 7 13 10 4 15 19 205.5.2随机选择主元随机选择主元 随机选主元算法随机选主元算法随机选主元算法随机选主元算法假假定定表表中中元元素素各各不不相相同同，并并且且随随机机选选择择主主元元，即即在在下下标标区区间间left,right中中随随机机选选择择一一个个下下标标r，以以该该下下标处标处的元素的元素为为主元。主元。【程序程序程序程序5 51313】SelectSelect函数函数函数函数templateResultCodeSortableList:Select1(T&x,intk)if(nn|k=0)returnO
39、utOfBounds;intleft=0,right=n;ln=INFTY;dointj=rand()%(right-left+1)+left;Swap(left,j);j=Partition(left,right);if(k=j+1)x=lj;returnSuccess;elseif(kj+1)right=j;elseleft=j+1;while(true);定理定理定理定理5 5 5 58 8 8 8 程序程序513的的Select算法的平均时间算法的平均时间A(n)=O(n)。算法的最坏情况算法的最坏情况时间时间复复杂杂度度O(n2)。5.5.3线性时间选择算法线性时间选择算法改进的选择
40、算法采用改进的选择算法采用二次取中法二次取中法二次取中法二次取中法(median of (median of medians rule)medians rule)确定主元确定主元【程序程序程序程序5 51414】 线性时间选择算法线性时间选择算法线性时间选择算法线性时间选择算法ResultCodeSortableList:Select(T&x,intk)if(nn|k=0)returnOutOfBounds;intj=Select(k,0,n-1,5);x=lj;returnSuccess;templateintSortableList:Select(intk,intleft,intright
41、,intr)intn=right-left+1;if(n=r)InsertSort(left,right);returnleft+k-1; for(inti=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);intj=Select(Ceil(n/r,2),left,left+(n/r)-1,r);Swap(left,j);j=Partition(left,right);if(k=j-left+1)returnj;elseif(kj-left+1)returnSelect(
42、k,left,j-1,r);elsereturnSelect(k-(j-left+1),j+1,right,r);5.5.4时间分析时间分析 以二次取中的中以二次取中的中间值间值mm为为主元，主元，经过经过一趟分一趟分划，左、右两个子表的大小均至多划，左、右两个子表的大小均至多为为：n nn/rn/r /2/2 r/2r/2 设设T(n)为为当当表表长长为为n时时执执行行程程序序514所所需需的的时时间间。T(n)由三部分由三部分时间组时间组成：成：T(n)T(n) T(T( n/5n/5 )+T(3n/4)+cn)+T(3n/4)+cn 用用用用归归归归纳纳纳纳法法法法容容容容易易易易证证证
43、证明明明明，T(n)T(n) 20cn20cn，n n 1 1是是是是线线线线性性性性时间时间时间时间的。的。的。的。 5.5.5允许重复元素的选择算法允许重复元素的选择算法由由于于允允许许包包含含相相同同元元素素，左左子子表表中中除除了了小小于于mm的的元元素素外外，还还包包含含与与mm相相同同值值的的元元素素。因因此此，左左子子表的大小至多可达表的大小至多可达n nn/rn/r /2/2 r/2r/2 +1/2+1/2 n/rn/r /2/2 r/2r/2 =n-1/2=n-1/2 n/rn/r /2/2 r/2r/2 容易用容易用归纳归纳法法证证明明对对于所有于所有n 90，T(n)T(
44、n) T(n/9)+T(7n/8)+cnT(n/9)+T(7n/8)+cn 72cn72cn，n n 90905.6斯特拉森矩阵乘法斯特拉森矩阵乘法 问题问题 矩阵相乘矩阵相乘矩阵乘积的矩阵乘积的StrassenStrassen算法算法C=AB=(cij)nn。 求求C=ABC=AB即即对对n n2 2个个元元素素c cijij进进行行计计算算，故故要要作作n n3 3次次乘乘法法。相相当当时时间间内内没没有有人人怀怀疑疑过过是是否否可可以以用用少少于于n n3 3次次乘乘法法来来完完成。其实不然，先以成。其实不然，先以n=2n=2的矩阵乘积为例。的矩阵乘积为例。对于矩阵对于矩阵则有：则有：共
45、需作共需作8次乘法和次乘法和4次加法。次加法。分治法求解大矩阵分治法求解大矩阵 C11A11B11+A12B21C12A11B12+A12B22C21A21B11+A22B21C22A21B12+A22B22一个四阶方阵可以看作由一个四阶方阵可以看作由4 4个二阶方阵组成个二阶方阵组成分治法求解大矩阵分治法求解大矩阵 C11A11B11+A12B21C12A11B12+A12B22C21A21B11+A22B21C22A21B12+A22B22一个一个一个一个n n n n阶方阵可以看作由阶方阵可以看作由阶方阵可以看作由阶方阵可以看作由4 4 4 4个个个个n/2n/2n/2n/2阶的方阵组成
46、，二个阶的方阵组成，二个阶的方阵组成，二个阶的方阵组成，二个n n n n阶方阵的乘积，转化为八个阶方阵的乘积，转化为八个阶方阵的乘积，转化为八个阶方阵的乘积，转化为八个n/2n/2n/2n/2阶方阵的乘积和阶方阵的乘积和阶方阵的乘积和阶方阵的乘积和4 4 4 4个个个个n/2n/2n/2n/2阶方阵的加法。阶方阵的加法。阶方阵的加法。阶方阵的加法。T(n)= (n3)定理定理定理定理5-15-1设设a,b,c和和k为常数，为常数，T(n)=aT(n/b)+cnk，T(1)=c，则，则，5.6.2斯特拉森分治法斯特拉森分治法P=(A11+A22)(B11+B22)Q=(A21+A22)B11R
47、=A11(B12-B22)S=A21(B21-B11)T=(A11+A12)B22U=(A21-A11)(B11+B12)V=(A12-A22)(B21+B22)C11=P+S-T+VC12=R+TC21=Q+SC22=P+R-Q+UT(n)= (nlog7)(n2.81) 2*2矩阵的最少乘法次数是矩阵的最少乘法次数是7。目前最好的矩阵乘法的时间上界是：目前最好的矩阵乘法的时间上界是：O(n2.376)。我们研究两个我们研究两个n位二进制数相乘的问题。用普通的方法位二进制数相乘的问题。用普通的方法运算，将乘数的每一位（由低位至高位）逐个去乘被运算，将乘数的每一位（由低位至高位）逐个去乘被乘数
48、，每乘一次将乘积与原来的积相加，然后乘数和乘数，每乘一次将乘积与原来的积相加，然后乘数和乘积移位一步，如此下去直至乘数的最高位运算完即乘积移位一步，如此下去直至乘数的最高位运算完即得出结果，这样运算共需得出结果，这样运算共需n2次一位乘一位运算，次一位乘一位运算，n(n-1)次一位加一位运算和次一位加一位运算和n次移位，假设两个一位数相乘，次移位，假设两个一位数相乘，两个一位数相加和任何数移位一步所需运算时间均为两个一位数相加和任何数移位一步所需运算时间均为O(1)，即均为常数。总运算复杂性为，即均为常数。总运算复杂性为O（n2）。）。大整数相乘大整数相乘现在用分治法来做。设现在用分治法来做。
49、设n=2r,将两个数都按位数划分将两个数都按位数划分成两段，如图所示，成两段，如图所示，这需要三次这需要三次n位的加法，一次位的加法，一次n步移位，一次步移位，一次n/2步步移位和四次移位和四次n/2位的乘法。位的乘法。设用分治法做两个设用分治法做两个n位数乘法的复杂性为位数乘法的复杂性为T（n），），因加法和移位都是因加法和移位都是O（n），），故：故：这样并没有显出其优越性，我们可以将其进一步这样并没有显出其优越性，我们可以将其进一步改进，增加一些加法运算以减少乘法运算。改进，增加一些加法运算以减少乘法运算。定理定理定理定理5-15-1设设a,b,c和和k为常数，为常数，T(n)=aT(n
50、/b)+cnk，T(1)=c，则，则，减少了乘法运算的次数。减少了乘法运算的次数。显然较普通方法更有效。这种思想同样可以用显然较普通方法更有效。这种思想同样可以用于十进制数的乘法中。于十进制数的乘法中。类似于上述例子，可以看出，一般情况下采用类似于上述例子，可以看出，一般情况下采用分治解决法划分子问题时，使各子问题的规模尽量分治解决法划分子问题时，使各子问题的规模尽量相等为好。此外，如果是逐层划分，采用递归形式相等为好。此外，如果是逐层划分，采用递归形式可以使程序简而明，分析起来也较为方便。可以使程序简而明，分析起来也较为方便。计算：计算：23483825=？循环赛日程表循环赛日程表 设设有有
51、n=2n=2k k个个运运动动员员要要进进行行网网球球循循环环赛赛。现现要要设设计计一一个满足以下要求的比赛日程表：个满足以下要求的比赛日程表： （1 1）每个选手必须与其他）每个选手必须与其他n-1n-1个选手各赛一次；个选手各赛一次； （2 2）每个选手一天只能赛一次；）每个选手一天只能赛一次； （3 3）循环赛一共进行）循环赛一共进行n-1n-1天。天。 按按此此要要求求可可将将比比赛赛日日程程表表设设计计成成有有n n行行和和n n列列的的一一个个表表。在在表表中中第第i i行行和和第第j j列列处处填填入入第第i i个个选选手手在在第第j j天天所所遇到的选手。遇到的选手。4个选手的
52、比赛日程表日程日程日程日程选手选手选手选手一一二二三三四四五五六六七七1234567821436587341278564321876556781234658721437856341287654321 按按分分治治策策略略，我我们们可可以以将将所所有有选选手手对对分分为为两两组组，n n个个选选手手的的比比赛赛日日程程表表就就可可以以通通过过为为n/2n/2个个选选手手设设计计的的比比赛赛日日程程表表来来决决定定。递递归归地地用用这这种种一一分分为为二二的的策策略略对对选选手手进进行行分分割割，直直到到只只剩剩下下2 2个个选选手手时时，比比赛赛日日程程表表的的制制定定就就变变得得很很简简单单。
53、这这时时只要让这只要让这2 2个选手进行比赛就可以了。个选手进行比赛就可以了。下下图图所所列列出出的的正正方方形形表表是是4个个选选手手的的比比赛赛日日程程表表。其其中中左左上上角角与与左左下下角角的的两两小小块块分分别别为为选选手手1至至选选手手2和和选选手手3至至选选手手4第第1天天的的比比赛赛日日程程。据据此此，将将左左上上角角小小块块中中的的所所有有数数字字按按其其相相对对位位置置抄抄到到右右下下角角，将将左左下下角角小小块块中中的的所所有有数数字字按按其其相相对对位位置置抄抄到到右右上上角角，这这样样我我们们就就分分别别安安排排好好了了选选手手1至至选选手手2和和选手选手3至选手至选手4在后在后2天的比赛日程。这种安排是符合要求的。天的比赛日程。这种安排是符合要求的。4个选手的比赛日程表依此思想容易将这个比赛日程表推广到具有任意依此思想容易将这个比赛日程表推广到具有任意多个选手的情形。下表是多个选手的情形。下表是8个选手的日程安排表。个选手的日程安排表。
