,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,10.3,递推方程的求解与应用,Hanoi,塔问题,递推方程的定义,二分归并排序算法的分析,快速排序算法的分析,递归树,分治算法分析的一般公式,1,10.3 递推方程的求解与应用Hanoi 塔问题1,Hanoi塔问题,Hanoi塔问,题：,从,A,柱将这些圆盘移到,C,柱上去.如果把一个圆盘从,一个柱子移到另一个柱子称作 1 次移动，在移动和放置,时允许使用,B,柱，但不允许大圆盘放到小圆盘的上面.问,把所有的圆盘的从,A,移到,C,总计需要多少次移动？,2,Hanoi塔问题Hanoi塔问题：2,算法设计与分析,算法,Hanoi,(,A,C,n,)/*,把,n,个盘子从,A,移到,C,1.,Hanoi(,A,B,n,-1),2.move(,A,C,)/*把1个盘子从,A,移到,C,3.Hanoi(,B,C,n,-1),移动,n,个盘子的总次数为,T,(,n,)，得到递推方程,T,(,n,)=2,T,(,n,1)+1.,T,(1)=1.,可以求得,T,(,n,)=2,n,1,1秒钟移动1次，64个盘子大约需要5000亿年,3,算法设计与分析算法 Hanoi(A,C,n)/*把,4,4,递推方程的定义,定义,10.5,设序列,a,0,a,1,a,n,简记为,a,n,一个把,a,n,与某些个,a,i,（,i,n,）联系起来的等式叫做关于序列,a,n,的,递推方程,.,实例：,Fibonacci数列：,f,n,=,f,n,-1,+,f,n,-2,初值,f,0,=1,f,1,=1,阶乘数列,a,n,，,a,n,=,n,!：,a,n,=,na,n,-1,a,1,=1,求解方法：迭代法,5,递推方程的定义定义10.5 设序列a0,a1,a,二分归并排序算法,算法Mergesort(,A,s,t,)/*排序数组,A,s,.,t,1.,m,(,t-s,)/2,2.,A,Mergesort(,A,s,m,)/*排序前半数组,3.,B,Mergesort(,A,s,+1,t,)/*排序后半数组,4.Merge(,A,B,)/*将排好序的,A,B,归并,假设,n,=2,k,，比较次数至多为,W,(,n,),W,(,n,)=2,W,(,n,/2)+,n,1,归并两个,n,/2大小数组的比较次数为,n,1,6,二分归并排序算法算法Mergesort(A,s,t)/,实例,输入,：,5,1,7,8,2,4,6,3,划分：,5,1,7,8,2,4,6,3,递归排序前半个数组:,5,1,7,8,1,5,7,8,递归排序后半个数组:,2,4,6,3,2,3,4,6,归并:,1,5,7,8,和,2,3,4,6,输出：,1,2,3,4,5,6,7,8,归并过程,1,5,7,8,2,3,4,6,7,实例157823467,求解递推方程,8,求解递推方程8,归纳法验证解,n,=1代入上述公式得,W,(1)=1 log1,1+1=0，,符合初始条件.,假设对于任何小于,n,的正整数,t,，,W,(,t,)都是正确的，将结果代入原递推方程的右边得,2,W,(,n,/2)+,n,1,=2(2,k,1,log2,k,1,2,k,1,+1)+2,k,1,=2,k,(,k,1),2,k,+2+2,k,1=,k,2,k,2,k,+1,=,n,log,n,n,+1=,W,(,n,),9,归纳法验证解n=1代入上述公式得9,快速排序算法,算法 Q,uicksort(,A,p,r,)/*排序数组,A,p,.,r,输入：,数组,A,p,.,r,输出：排好序的数组,A,1.if,p,r,2.then,q,Partition(,A,p,r,)/*以,A,p,为准划分,A,3.,A,p,A,q,/*,A,p,与,A,q,交换,4.Quicksort(,A,p,q,-1)/*对子数组递归排序,5.Quicksort(,A,q,+1,r,),10,快速排序算法算法 Quicksort(A,p,r)/*,Partition(,A,p,r,),1.,x,A,p,2.,i,p,3.,j,r,+1,4.while true do,5.repeat,j,j,1,6.until,A,j,x,/*左边第1个比,A,p,大的,A,i,9.if,i,j,10.then,A,i,A,j,/*交换,A,j,与,A,i,11.else return,j,划分过程,11,Partition(A,p,r)划分过程11,27,99,0 8 13 64 86 16 7 10 88,25,90,27,25 0 8 13,64,86 16 7,10,88 99 90,27,25 0 8 13 10,86,16,7,64 88 99 90,27,25 0 8 13 10 7,16,86 64 88 99 90,16,25 0 8 13 10 7,86 64 88 99 90,27,12,27 99 0 8 13 64,平均时间复杂度,T,(,n,)为对数组的各种输入平均做的比较次数,将输入按照,A,p,在排好序后的位置分别为1,2,n,进行分类.假设每类输入出现的概率相等,A,p,处位置1，划分后子问题规模分别为0和,n,-1,A,p,处位置,n,，划分后子问题规模分别为,n,-1和0,n,种输入的平均复杂度为,13,平均时间复杂度T(n)为对数组的各种输入平均做的比较次数13,递推方程求解,差消法化简,14,递推方程求解差消法化简14,迭代,15,迭代15,用积分近似,.,16,用积分近似.16,递归树,W,(,n,),W,(,n,/2),W,(,n,/2),n,1,n,/2-1,W,(,n,/4),n,1,n,/2-1,W,(,n,/4),.,17,递归树W(n)W(n/2)W(n/2)n1n/2-1W(n,n,-1,n,/2-1,n,/2-1,n,/4-1,n,/4-1,n,/4-1,n,/4-1,.,1 1 1 1 1 1 1 1 1 1,n-,1,n,-2,n,-4,n,-2,k,1,18,n-1n/2-1n/2-1n/4-1n/4-1n/4-1n/,分治算法的常用递推公式,其中,a,为子问题个数，,n/b,为子问题规模，,d,(,n,)为分解成子问题或组合解的代价,方程的解为：,19,分治算法的常用递推公式其中a为子问题个数，n/b为子问题规模,Case1,d,(,n,)=,c,迭代,20,Case1 d(n)=c 迭代20,Case2,d,(,n,)=,cn,21,Case2 d(n)=cn 21,应用实例,二分归并,二分查找,a,=2，,b,=2，,d,(,n,)=,O,(,n,),T,(,n,)=,O,(,n,log,n,),a,=1，,b,=2，,d,(,n,)=,O,(1),T,(,n,)=,O,(log,n,),22,应用实例二分归并a=2，b=2，d(n)=O(n)T,