离散数学：第10章 组合分析初步2

1、110.3 递推方程的求解与应用递推方程的求解与应用nHanoi 塔问题塔问题n递推方程的定义递推方程的定义n二分归并排序算法的分析二分归并排序算法的分析n快速排序算法的分析快速排序算法的分析n递归树递归树n分治算法分析的一般公式分治算法分析的一般公式2HanoiHanoi塔问题塔问题Hanoi塔问题：塔问题：从从A柱将这些圆盘移到柱将这些圆盘移到C柱上去柱上去. 如果把一个圆盘从如果把一个圆盘从一个柱子移到另一个柱子称作一个柱子移到另一个柱子称作 1 次移动，在移动和放置次移动，在移动和放置时允许使用时允许使用B柱，但不允许大圆盘放到小圆盘的上面柱，但不允许大圆盘放到小圆盘的上面. 问问把所

2、有的圆盘的从把所有的圆盘的从A移到移到C总计需要多少次移动？总计需要多少次移动？3算法设计与分析算法设计与分析算法算法 Hanoi (A,C,n) /*把把n个盘子从个盘子从A移到移到C1. Hanoi (A,B,n-1) 2. move (A,C) /*把把1个盘子从个盘子从A移到移到C3. Hanoi (B,C,n-1) 移动移动n个盘子的总次数为个盘子的总次数为T(n) ，得到递推方程，得到递推方程 T(n) = 2T(n 1) +1. T(1)=1. 可以求得可以求得 T(n)=2n 11秒钟移动秒钟移动1次，次，64个盘子大约需要个盘子大约需要5000亿年亿年4（等比级数求和）（等比

3、级数求和）代入初值代入初值的项替换的项替换被含被含的项替换的项替换被含被含12)(12.22212.22)1(2.122)3(2)3()2(12 1)3(2212)2(2)2()1(1 1)2(2 21)1(2)(3213212322 nnnnnnnTnTnTnTnTnTnTnTnTnTnT5递推方程的定义递推方程的定义定义定义10.5 设序列设序列a0, a1, , an, , 简记为简记为an, 一一个把个把an与某些个与某些个ai（in）联系起来的等式叫做关）联系起来的等式叫做关于序列于序列an的的递推方程递推方程. 实例：实例： Fibonacci数列：数列： fn=fn-1+fn-2

4、, 初值初值 f0=1, f1=1 阶乘数列阶乘数列an，an=n!：an=nan-1, a1=1 求解方法：迭代法求解方法：迭代法 0)1(2),()(2)(11TnnOiTnnTni6二分归并排序算法二分归并排序算法算法算法Mergesort(A,s,t) /*排序数组排序数组As.t1. m(t-s)/22. AMergesort(A,s,m) /*排序前半数组排序前半数组3. BMergesort(A,s+1,t) /*排序后半数组排序后半数组4. Merge(A,B) /*将排好序的将排好序的A,B归并归并假设假设n=2k，比较次数至多为，比较次数至多为W(n) W(n)=2W(n/

5、2)+n 1归并两个归并两个n/2大小数组的比较次数为大小数组的比较次数为n 17实例实例 输入输入：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 归并过程归并过程157823468求解递推方程求解递推方程1log122)12.22(2(1)2.1222

6、22)2(2122212)2(221222)2(21212)2(2 2 12 )2 (2 )(2123323222121 nnnkkWWWWWWnWkkkkkkkkkkkkkkkkkkkkkk9归纳法验证解归纳法验证解nn=1代入上述公式得代入上述公式得 W(1)=1 log1 1+1=0， 符合初始条件符合初始条件. n假设对于任何小于假设对于任何小于n的正整数的正整数t，W(t)都是正确的，都是正确的，将结果代入原递推方程的右边得将结果代入原递推方程的右边得 2W(n/2)+n 1 =2(2k 1 log2k 1 2k 1+1)+2k 1 =2k(k 1) 2k+2+2k 1=k2k 2k

7、+1 = nlogn n+1=W(n) 10快速排序算法快速排序算法算法算法 Q Quicksort(A,p,r) /*排序数组排序数组Ap.r输入：输入：数组数组Ap.r输出：排好序的数组输出：排好序的数组A 1. if p r 2. then qPartition(A, p, r) /*以以Ap为准划分为准划分A 3. ApAq /*Ap与与Aq交换交换 4. Quicksort(A,p,q-1) /*对子数组递归排序对子数组递归排序 5. Quicksort(A,q+1,r)11Partition(A,p,r) 1. x Ap 2. i p 3. j r+1 4. while true

8、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 划分过程划分过程1227 99 0 8 13 64 86 16 7 10 88 25 9027 25 0 8 13 64 86 16 7 10 88 99 9027 25 0 8 13 10 86 16 7 64 88 99 9027 25 0 8 13 10 7 16 86 64 88 99 9016 25 0 8 13 10 786 64 88 99 902713平

9、均时间复杂度平均时间复杂度nT(n)为对数组的各种输入平均做的比较次数为对数组的各种输入平均做的比较次数 将输入按照将输入按照Ap在排好序后的位置分别为在排好序后的位置分别为1, 2, , n进行分类进行分类. 假设每类输入出现的概率相等假设每类输入出现的概率相等nAp处位置处位置1，划分后子问题规模分别为，划分后子问题规模分别为0和和n-1 Ap处位置处位置n，划分后子问题规模分别为，划分后子问题规模分别为n-1和和0 nn 种输入的平均复杂度为种输入的平均复杂度为)()(2)()0()1(.)2()1()1()0(1)(11nOiTnnOTnTnTTnTTnnTni 14递推方程求解递推方

10、程求解 0)1(2),()(2)(11TnnOiTnnTni 2122111)()(21)()1()(2)(nininciTnTnccniTnnT为为某某个个常常数数差消法化简差消法化简)()1(21)()1()(nOnTnTnnnT )()1()1()(nOnTnnnT 15迭代迭代 31.1112)1(31.11111)2(1)1(1)(nncTnncncncnnTcncnnTnnT为为某某个个常常数数16用积分近似用积分近似)(log2ln)1ln(ln131.1111212nOnxdxxnnnn )log()(nnOnT .17递归树递归树 0 (1)2 , 1 ) /2 (2 )(W

11、nnnWnWkW(n)W(n/2)W(n/2)n 1n/2-1W(n/4)n 1n/2-1W(n/4).18n-1n/2-1n/2-1n/4-1n/4-1n/4-1n/4-1.1 1 1 1 1 1 1 1 1 1n-1n-2n-4n-2k 11log)12()2.21()2(.)2()1(11 nnnnknknnnkkk19分治算法的常用递推公式分治算法的常用递推公式 1)1()()/()(TbnndbnaTnTk其中其中a为子问题个数，为子问题个数，n/b为子问题规模，为子问题规模，d(n)为分解成为分解成子问题或组合解的代价子问题或组合解的代价方程的解为：方程的解为： banObannObanOnTcnndanOanOnTcndaabb)()log()()(:)(1)(log1)()(:)(loglog20)/()()/(.)/()/()/(.)()/()/()(10221122ikiikkkkkkkbndaandbnadbnabndabnTandbnadbnTanT ankbbnaaloglog Case1 d(n)=c 1)(log1)()(11)(loganOkcaanOaOaacanTkakkkb迭代迭代21Case2 d(n)=cn banObabacababacnabannOcnknbanObabacnnbacnabcnaanTakkkkkkakiikik