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

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

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

2、推方程的其他解法递推方程的其他解法10.1.5 递推方程与递归算法递推方程与递归算法3本讲稿第三页，共四十一页递推方程的定义递推方程的定义定义定义10.1 设序列设序列 a0,a1,an,简记为简记为 an.一个把一个把 an 与与某些个某些个ai(i028本讲稿第二十八页，共四十一页实例实例解解 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

3、本讲稿第二十九页，共四十一页迭代归纳法迭代归纳法归并排序归并排序例例1530本讲稿第三十页，共四十一页迭代归纳法迭代归纳法错位排列错位排列例例16 Dn=(n1)(Dn1+Dn2)解：解：31本讲稿第三十一页，共四十一页差消法差消法化简递推方程化简递推方程例例1732本讲稿第三十二页，共四十一页积分近似积分近似33本讲稿第三十三页，共四十一页递归树递归树二分归并排序二分归并排序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

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

5、，个数，d(n)为为分解及分解及综综合的代价合的代价38本讲稿第三十八页，共四十一页分治策略与递归算法分治策略与递归算法(续续)(1)d(n)=c 实例：实例：二分搜索二分搜索 W(n)=W(n/2)+1 a=1,b=2,d(n)=c W(n)=O(logn)39本讲稿第三十九页，共四十一页分治策略与递归算法分治策略与递归算法(续续)(2)d(n)=cn 实例：归并排序实例：归并排序 W(n)=2W(n/2)+n 1 a=2,b=2,d(n)=O(n),W(n)=O(nlogn)40本讲稿第四十页，共四十一页实例实例位乘问题位乘问题位乘问题：位乘问题：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本讲稿第四十一页，共四十一页