第5章 减治法

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,算法设计与分析,清华大学出版社,第,5,章 减治法,5.1,减治法的设计思想,5.2,查找问题中的减治法,5.3,排序问题中的减治法,5.4,组合问题中的减治法,5.1,减治法的设计思想,规模为,n,的原问题的解与较小规模（通常是,n,/2,）,的子问题的解之间具有关系：,（,1,）原问题的解只存在于其中一个较小规模的子问题中；,（,2,）原问题的解与其中一个较小规模的解之间存在某种对应关系。,由于原问题的解与较小规模的子问题的解之间存在这种关系，所以，只需求解其中一个较小规模的子问题就可以得到原问题的解。,子问题,的规模是,n,/2,子问题的解,原问题的解,原问题,的规模是,n,减治法的设计思想,例：计算,a,n,的值，,应用减治技术得到如下计算方法：,应用分治法得到,a,n,的计算方法是：,O,(,log,2,n,),O,(,n,log,2,n,),=,=,-,且是奇数,且是偶数,1,),(,1,),(,1,2,2,),1,(,2,2,n,a,a,n,a,n,a,a,n,n,n,所以，通常来说，应用减治法处理问题的效率是很高的，一般是,O,(,log,2,n,),数量级。,减治法只对一个子问题求解，并且不需要进行解的合并。应用减治法（例如减半法）得到的算法通常具有如下递推式：,5.2,查找问题中的减治法,5.2.1,折半查找,5.2.2,二叉查找树,基本思想：在有序表中，取中间记录作为比较对象，若给定值与中间记录的关键码相等，则查找成功；若给定值小于中间记录的关键码，则在中间记录的左半区继续查找；若给定值大于中间记录的关键码，则在中间记录的右半区继续查找。不断重复上述过程，直到查找成功，或所查找的区域无记录，查找失败。,5.2.1,折半查找,r,1,r,mid,-,1,r,mid,r,mid,+1,r,n,（,mid,=,(,1+,n,),/2,）,如果,k,r,mid,查找这里,k,例：查找值为,14,的记录的过程：,0 1 2 3 4 5 6 7 8 9 10 11 12 13,7 14 18 21 23 29 31 35 38 42 46 49 52,low=1,high=13,mid=7,high=6,mid=3,high=2,mid=1,3114,1,814,714,low=2,mid=2,14=,14,算法,5.1,折半查找,1.low=1,；,high=n,；,/,设置初始查找区间,2.,测试查找区间,low,，,high,是否存在，若不存在，则查找失败；,否则,3.,取中间点,mid=,(,low+high,),/2;,比较,k,与,rmid,，,有以下三种情况：,3.1,若,krmid,，则,low=mid+1,；,查找在右半区进行，转,2,；,3.3,若,k=rmid,，,则查找成功，返回记录在表中位置,mid,；,伪代码,判定树,描述折半查找的判定过程。,长度为,n,的判定树的构造方法为：,（,1,）当,n,=0,时，判定树为空；,（,2,）当,n,0,时，判定树的根结点是有序表中序号为,mid=(n+1)/2,的记录，根结点的左子树是与有序表,r1 rmid-1,相对应的判定树，根结点的右子树是与,rmid+1,rn,相对应的判定树。,具有,11,个结点的判定树,6,3,1,2,5,4,8,11,10,7,9,在表中查找任一记录的过程，即是判定树中从根结点到该记录结点的路径，和给定值的比较次数等于该记录结点在树中的层数。具有,n,个结点的判定数的深度为 。,5.2.2,二叉查找树,由二叉排序树的定义，在二叉排序树,root,中查找给定值,k,的过程是：,若,root,是空树，则查找失败；,若,k,根结点的值，则查找成功；,否则，若,k,根结点的值，则在,root,的左子树上查找；,否则，在,root,的右子树上查找；,上述过程一直持续到,k,被找到或者待查找的子树为空，如果待查找的子树为空，则查找失败。,二叉排序树的查找效率就在于只需要查找两个子树之一。,(a),按,63,90,55,58,70,42,10,45,83,67 (b),按,55,42,10,70,63,58,83,67,90,45,的顺序构造的二叉排序树 的顺序构造的二叉排序树,58,42,70,90,63,45,55,83,67,10,10,83,63,70,55,45,42,67,58,90,二叉排序树的结点结构为：,struct,BiNode,int,data;/,结点的值，假设查找集合的元素为整型,BiNode,*,lchild,*,rchild,;/,指向左、右子树的指针,;,算法,5.2,二叉排序树的查找,BiNode,*,SearchBST(BiNode,*root,int,k),if(root=NULL)return NULL,；,else if(root-data=k)return root;,else if(kdata)return,SearchBST(root,-,lchild,k);,else return,SearchBST(root,-,rchild,k);,C+描述,在二叉排序树上查找关键码等于给定值的结点的过程，恰好走了一条从根结点到该结点的路径，和给定值的比较次数等于给定值的结点在二叉排序树中的层数，比较次数最少为,1,次（即整个二叉排序树的根结点就是待查结点），最多不超过树的深度。具有,n,个结点的二叉树的深度至少是 ，至多是,n,，,所以，二叉排序树的查找性能在,O,(,log,2,n,),和,O,(,n,),之间。,5.3,排序问题中的减治法,5.3.1,堆排序,5.3.2,选择问题,5.3.1,堆排序,以结点的编号作为下标，将堆用顺序存储结构（即数组）来存储，则堆对应于一组序列。,(a),大根堆及其对应的序列,(b),小根堆及其对应的序列,47 35 26 20 18 7 13 10,7 10 13 18 35 26 47 20,47,35,26,13,18,20,7,10,26,10,13,47,35,18,7,20,堆排序的基本思想是：首先将待排序的记录序列构造成一个堆，此时，选出了堆中所有记录的最大者即堆顶记录，然后将它从堆中移走（通常将堆顶记录和堆中最后一个记录交换），并将剩余的记录再调整成堆，这样又找出了次大的记录，以此类推，直到堆中只有一个记录为止。,r,1,r,2,r,i,r,i,+1,r,n,-,1,r,n,无序区 有序区,为一个堆 已经位于最终位置,堆顶和堆中最后,一个记录交换,堆调整问题,：将一个无序序列调整为堆,（,1,）筛选法调整堆,关键问题：完全二叉树中，根结点的左右子树均是堆，如何调整根结点，使整个完全二叉树成为一个堆？,(,a)28,与,35,交换,(b)28,与,32,交换,(c),将,28,筛到叶子,28,32,18,20,12,18,20,12,35,32,18,20,12,35,35,28,32,28,假设当前要筛选结点的编号为,k,，,堆中最后一个结点的编号为,n,，,并且结点,k,的左右子树均是堆（即,rk+1 rn,满足堆的条件），则筛选算法用伪代码可描述为：,算法,5.3,筛选法调整堆,1.,设置,i,和,j,，,分别指向当前要筛选的结点和要筛选结点的左孩子；,2.,若结点,i,已是叶子，则筛选完毕；否则，比较要筛选结点的左右 孩子结点，并将,j,指向关键码较大的结点；,3.,将要筛选结点,i,的关键码与结点,j,的关键码进行比较，有以下两种情况：,3.1,如果结点,i,的关键码大，则完全二叉树已经是堆；,3.2,否则将,ri,与,rj,交换；令,i=j,，,转步骤,2,继续进行筛选；,伪代码,时间性能是,O,(log,2,n,),。,算法,5.4,筛选法调整堆,void,SiftHeap,(,int,r,int,k,int,n,),i=k;j=2*i;/,置,i,为要筛的结点，,j,为,i,的左孩子,while,(,j=n,),/,筛选还没有进行到叶子,if,(,jn&rjrj,),/,根结点已经大于左右孩子中的较大者,break;,else,rirj;/,将根结点与结点,j,交换,i=j;j=2*i;/,被筛结点位于原来结点,j,的位置,C+描述,32,18,20,12,40,35,8,28,20,32,18,20,12,40,8,20,35,28,18,20,12,40,8,20,35,28,32,(a)35,与,28,交换,(b)35,与,32,交换,(c)3540,调整完毕,（,2,）插入法调整堆,关键问题是：在堆中插入一个结点，如何调整被插入结点，使整个完全二叉树仍然是一个堆？,假设当前堆中有,k,个结点，则要插入结点的编号为,k+1,，,插入法调整堆的算法如下：,算法,5.5,插入法调整堆,1.,设,i,指向当前要插入的结点；,2.,若结点,i,是整个堆的根结点，则调整完毕；,3,否则，设,j,指向结点,i,的双亲结点；将结点,i,与结点,j,进行比较；,3.1,如果结点,i,的关键码小，则完全二叉树已经是堆，调整完毕；,3.2,否则将,ri,与,rj,交换；令,i=j,，,转步骤,2,继续进行调整；,伪代码,时间复杂性为,O,(log,2,n,),。,算法,5.6,插入法调整堆,void,InsertHeap,(,int,r,int,k,),/,堆中有,k,个结点，现插入一个新结点,k+1,i=k+1;/,置,i,为要插入的结点,while(i!=1),j=i/2;/j,为,i,的双亲结点,if,(,rirj,),/,待插入结点已小于根结点，调整结束,break;,else,rirj;/,将根结点与结点,j,交换,i=j;/,待插入点位于原来结点,j,的位置,C+描述,设无序序列,T,=(,r,1,r,2,r,n,),，,T,的第,k,（,1,k,n,）,小元素定义为,T,按升序排列后在第,k,个位置上的元素。给定一个序列,T,和一个整数,k,，寻找,T,的第,k,小元素的问题称为,选择问题,。特别地，将寻找第,n,/2,小元素的问题称为,中值问题,。,5.3.2,选择问题,（,1,）若,k,=,s,，则,r,s,就是第,k,小元素；,（,2,）若,k,s,，,则第,k,小元素一定在序列,r,s,+1,r,j,中；,r,i,r,k,r,s,-,1,r,s,r,s,+1,r,j,均,r,s,轴值 均,r,s,r,i,r,s,-,1,r,s,r,s,+1,r,k,r,j,均,r,s,轴值 均,r,s,(a),若,k,s,，则,r,k,在右半区,考虑快速排序中的划分过程，一般情况下，设待划分的序列为,r,i,r,j,，选定一个轴值将序列,r,i,r,j,进行划分，使得比轴值小的元素都位于轴值的左侧，比轴值大的元素都位于轴值的右侧，假定轴值的最终位置是,s,，则：,选择问题的例子,:,5 3 8 1 4 6 9 2 7,选择问题的查找过程示例（,查找第,4,小元素）,以,5,为轴值划分序列,42,，只在右侧查找,以,4,为轴值划分序列,4,4,，轴值即为第,4,小元素,2 3 4 1,5,6 9 8 7,2 3 4 1,1,2,4 3,4 3,3,4,算法,5.7,选择问题,1.i=1;j=n;/,设置初始查找区间,2.,以,ri,为轴值对序列,rirj,进行一次划分，得到轴值的位置,s;,3.,将轴值位置,s,与,k,比较,3.1,如果,k=s,，,则将,rs,作为结果返回；,3.2,否则，如果,k1),i=i/2;,for(j=0;j,d,e,f,a,b,c,d,e,f,a,b,c,d,e,f,，,可以肯定这六枚硬币中必有一枚为假币，同时也说明,g,，,h,为真币。这时可将天平两端各去掉一枚硬币，假设去掉,c,和,f,，,同时将天平两端的硬币各换一枚，假设硬币,b,，,e,作了互换，然后进行第二次比较，比较的结果同样可能有三种：,a