《离散完整课件10.3章节》由会员分享，可在线阅读，更多相关《离散完整课件10.3章节（22页珍藏版）》请在金锄头文库上搜索。
1、1,10.3 递推方程的求解与应用,Hanoi 塔问题 递推方程的定义 二分归并排序算法的分析 快速排序算法的分析 递归树 分治算法分析的一般公式,2,Hanoi塔问题,Hanoi塔问题： 从A柱将这些圆盘移到C柱上去. 如果把一个圆盘从 一个柱子移到另一个柱子称作 1 次移动，在移动和放置 时允许使用B柱，但不允许大圆盘放到小圆盘的上面. 问 把所有的圆盘的从A移到C总计需要多少次移动？,3,算法设计与分析,算法 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
2、),移动n个盘子的总次数为T(n) ，得到递推方程 T(n) = 2T(n1) +1. T(1)=1. 可以求得 T(n)=2n 1 1秒钟移动1次，64个盘子大约需要5000亿年,4,5,递推方程的定义,定义10.5 设序列a0, a1, , an, , 简记为an, 一个把an与某些个ai（in）联系起来的等式叫做关于序列an的递推方程. 实例： Fibonacci数列： fn=fn-1+fn-2, 初值 f0=1, f1=1 阶乘数列an，an=n!：an=nan-1, a1=1 求解方法：迭代法,6,二分归并排序算法,算法Mergesort(A,s,t) /*排序数组Ast 1. m(
3、t-s)/2 2. AMergesort(A,s,m) /*排序前半数组 3. BMergesort(A,s+1,t) /*排序后半数组 4. Merge(A,B) /*将排好序的A,B归并,假设n=2k，比较次数至多为W(n) W(n)=2W(n/2)+n1 归并两个n/2大小数组的比较次数为n1,7,实例 输入：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,
4、6 输出：1, 2, 3, 4, 5, 6, 7, 8 归并过程,1,5,2,3,4,6,8,求解递推方程,9,归纳法验证解,n=1代入上述公式得 W(1)=1 log11+1=0， 符合初始条件. 假设对于任何小于n的正整数t，W(t)都是正确的，将结果代入原递推方程的右边得 2W(n/2)+n1 =2(2k1 log2k12k1+1)+2k1 =2k(k1)2k+2+2k1=k2k2k+1 = nlognn+1=W(n),10,快速排序算法,算法 Quicksort(A,p,r) /*排序数组Apr 输入：数组Apr 输出：排好序的数组A 1. if p r 2. then qPartit
5、ion(A, p, r) /*以Ap为准划分A 3. ApAq /*Ap与Aq交换 4. Quicksort(A,p,q-1) /*对子数组递归排序 5. Quicksort(A,q+1,r),11,Partition(A,p,r) 1. x Ap 2. i p 3. j r+1 4. while true do 5. repeat j j 1 6. until A j x /*左边第1个比Ap大的Ai 9. if i j 10. then A i A j /*交换Aj与Ai 11. else return j,划分过程,12,27 99 0 8 13 64 86 16 7 10 88 25
6、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,13,平均时间复杂度,T(n)为对数组的各种输入平均做的比较次数 将输入按照Ap在排好序后的位置分别为1, 2, , n进行分类. 假设每类输入出现的概率相等 Ap处位置1，划分后子问题规模分别为0和n-1 Ap处位置n，划分后子问题规模分别为n-1和0 n 种输入的平均复杂度为,14,递推方程求解,差消法化简,15,迭代,16,用积分近似,.,17,递归树,18,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-2k1,19,分治算法的常用递推公式,其中a为子问题个数，n/b为子问题规模，d(n)为分解成子问题或组合解的代价 方程的解为：,20,Case1 d(n)=c,迭代,21,Case2 d(n)=cn,22,应用实例,二分归并 二分查找,a=2，b=2，d(n)=O(n) T(n)=O(nlogn),a=1，b=2，d(n)=O(1) T(n)=O(logn),
