离散数学--.递推方程与生成函数精.ppt

《离散数学--.递推方程与生成函数精.ppt》由会员分享，可在线阅读，更多相关《离散数学--.递推方程与生成函数精.ppt（41页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、离散数学离散数学-.递推方程递推方程与生成函数与生成函数1第1页，本讲稿共41页第第10章章 递推方程与生成函数递推方程与生成函数10.1 递推方程及其应用递推方程及其应用10.2 生成函数及其应用生成函数及其应用10.3 指数生成函数及其应用指数生成函数及其应用10.4 Catalan数与数与Stirling数数2第2页，本讲稿共41页10.1 递推方程及其应用递推方程及其应用10.1.1 递推方程的定义及实例递推方程的定义及实例10.1.2 常系数线性齐次递推方程的求解常系数线性齐次递推方程的求解10.1.3 常系数线性非齐次递推方程的求解常系数线性非齐次递推方程的求解10.1.4 递推方

2、程的其他解法递推方程的其他解法10.1.5 递推方程与递归算法递推方程与递归算法3第3页，本讲稿共41页递推方程的定义递推方程的定义定义定义10.1 设序列设序列 a0,a1,an,简记为简记为 an.一个把一个把 an 与与某些个某些个ai(i028第28页，本讲稿共41页实例实例解解 H(k)=2 H(k1)+2k1 H(1)=1 令令 H*(k)=P1k2k+P2,解得解得 P1=P2=1 H*(k)=k2k+1通解通解 H(k)=c 2k+k2k+1 代入初值得代入初值得 c=1 H(k)=2k+k2k+1 W(n)=n log n n+1 例例1414 归并排序归并排序29第29页，

3、本讲稿共41页迭代归纳法迭代归纳法归并排序归并排序例例1530第30页，本讲稿共41页迭代归纳法迭代归纳法错位排列错位排列例例16 Dn=(n1)(Dn1+Dn2)解：解：31第31页，本讲稿共41页差消法差消法化简递推方程化简递推方程例例1732第32页，本讲稿共41页积分近似积分近似33第33页，本讲稿共41页递归树递归树二分归并排序二分归并排序T(n)n-1T(n/2)T(n/2)n/2-1 n/2-1T(n/4)T(n/4)T(n/4)T(n/4)n/4-1 n/4-1 n/4-1 n/4-1.1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 T(n)=nk(1+2+2k

4、 1)=nk (2k 1)=n log n n+1 n 1n 2n 4.n 2k 1k层层34第34页，本讲稿共41页(1)T(n)=C,左左边边=O(1)尝试法尝试法例例18 (2)T(n)=cn,左左边边=cn,35第35页，本讲稿共41页尝试法尝试法(续续)(3)T(n)=cn2,左边左边=cn2(4)T(n)=cnlogn,左边左边=cnlogn 36第36页，本讲稿共41页积分近似积分近似37第37页，本讲稿共41页分治策略与递归算法分治策略与递归算法n为输为输入入规规模，模，n/b为为子子问题输问题输入入规规模，模，a为为子子问题问题个数，个数，d(n)为为分解及分解及综综合的代价

5、合的代价38第38页，本讲稿共41页分治策略与递归算法分治策略与递归算法(续续)(1)d(n)=c 实例：实例：二分搜索二分搜索 W(n)=W(n/2)+1 a=1,b=2,d(n)=c W(n)=O(logn)39第39页，本讲稿共41页分治策略与递归算法分治策略与递归算法(续续)(2)d(n)=cn 实例：归并排序实例：归并排序 W(n)=2W(n/2)+n 1 a=2,b=2,d(n)=O(n),W(n)=O(nlogn)40第40页，本讲稿共41页实例实例位乘问题位乘问题位乘问题：位乘问题：X,Y 为为 n 位二进制数，位二进制数，n=2k,求求 XY 一般方法：一般方法：W(n)=O(n2)分治法：令分治法：令X=A2n/2+B,Y=C2n/2+D,则则 XY=AC 2n+(AD+BC)2n/2+BD W(n)=4 W(n/2)+cn W(1)=1 a=4，b=2,W(n)=O(nlog4)=O(n2)变换：变换：AD+BC=(A B)(D C)+AC+BD W(n)=3 W(n/2)+cn W(1)=1 a=3，b=2,W(n)=O(nlog3)=O(n1.59)41第41页，本讲稿共41页