《离散数学--.递推方程与生成函数精选PPT.ppt》由会员分享，可在线阅读，更多相关《离散数学--.递推方程与生成函数精选PPT.ppt（41页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
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第
3、29页，此课件共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)=
4、nk(1+2+2k 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页哦