离散数学--.递推方程与生成函数PPT讲稿.ppt

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

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

2、非齐次递推方程的求解10.1.4 递推方程的其他解法递推方程的其他解法10.1.5 递推方程与递归算法递推方程与递归算法3第3页，共41页，编辑于2022年，星期日递推方程的定义递推方程的定义定义定义10.1 设序列设序列 a0,a1,an,简记为简记为 an.一个把一个把 an 与与某些个某些个ai(i028第28页，共41页，编辑于2022年，星期日实例实例解解 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

3、 W(n)=n log n n+1 例例1414 归并排序归并排序29第29页，共41页，编辑于2022年，星期日迭代归纳法迭代归纳法归并排序归并排序例例1530第30页，共41页，编辑于2022年，星期日迭代归纳法迭代归纳法错位排列错位排列例例16 Dn=(n1)(Dn1+Dn2)解：解：31第31页，共41页，编辑于2022年，星期日差消法差消法化简递推方程化简递推方程例例1732第32页，共41页，编辑于2022年，星期日积分近似积分近似33第33页，共41页，编辑于2022年，星期日递归树递归树二分归并排序二分归并排序T(n)n-1T(n/2)T(n/2)n/2-1 n/2-1T(n/

4、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 1)=nk (2k 1)=n log n n+1 n 1n 2n 4.n 2k 1k层层34第34页，共41页，编辑于2022年，星期日(1)T(n)=C,左左边边=O(1)尝试法尝试法例例18 (2)T(n)=cn,左左边边=cn,35第35页，共41页，编辑于2022年，星期日尝试法尝试法(续续)(3)T(n)=cn2,左边左边=cn2(4)T(n)=cnlogn,左边左边=cnlogn 36第36页，共41页

5、，编辑于2022年，星期日积分近似积分近似37第37页，共41页，编辑于2022年，星期日分治策略与递归算法分治策略与递归算法n为输为输入入规规模，模，n/b为为子子问题输问题输入入规规模，模，a为为子子问题问题个数，个数，d(n)为为分解及分解及综综合的代价合的代价38第38页，共41页，编辑于2022年，星期日分治策略与递归算法分治策略与递归算法(续续)(1)d(n)=c 实例：实例：二分搜索二分搜索 W(n)=W(n/2)+1 a=1,b=2,d(n)=c W(n)=O(logn)39第39页，共41页，编辑于2022年，星期日分治策略与递归算法分治策略与递归算法(续续)(2)d(n)=

6、cn 实例：归并排序实例：归并排序 W(n)=2W(n/2)+n 1 a=2,b=2,d(n)=O(n),W(n)=O(nlogn)40第40页，共41页，编辑于2022年，星期日实例实例位乘问题位乘问题位乘问题：位乘问题：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页，编辑于2022年，星期日