离散数学--10.1递推方程与生成函数.ppt_第1页
离散数学--10.1递推方程与生成函数.ppt_第2页
离散数学--10.1递推方程与生成函数.ppt_第3页
离散数学--10.1递推方程与生成函数.ppt_第4页
离散数学--10.1递推方程与生成函数.ppt_第5页
已阅读5页，还剩36页未读， 继续免费阅读

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

1,第10章递推方程与生成函数,2,第10章递推方程与生成函数,10.1递推方程及其应用10.2生成函数及其应用10.3指数生成函数及其应用10.4Catalan数与Stirling数,3,10.1递推方程及其应用,10.1.1递推方程的定义及实例10.1.2常系数线性齐次递推方程的求解10.1.3常系数线性非齐次递推方程的求解10.1.4递推方程的其他解法10.1.5递推方程与递归算法,4,递推方程的定义,定义10.1设序列a0,a1,an,简记为an.一个把an与某些个ai(i0,29,实例,解H(k)=2H(k1)+2k1H(1)=1令H*(k)=P1k2k+P2,解得P1=P2=1H*(k)=k2k+1通解H(k)=c2k+k2k+1代入初值得c=1H(k)=2k+k2k+1W(n)=nlognn+1,例14归并排序,30,迭代归纳法归并排序,例15,31,迭代归纳法错位排列,例16Dn=(n1)(Dn1+Dn2),解：,32,差消法化简递推方程,例17,33,积分近似,34,递归树二分归并排序,T(n),T(n/2)T(n/2),T(n/4)T(n/4)T(n/4)T(n/4),1111111111111111,T(n)=nk(1+2+2k1)=nk(2k1)=nlognn+1,35,(1)T(n)=C,左边=O(1),尝试法,例18,(2)T(n)=cn,左边=cn,36,尝试法(续),(3)T(n)=cn2,左边=cn2,(4)T(n)=cnlogn,左边=cnlogn,37,积分近似,38,分治策略与递归算法,n为输入规模，n/b为子问题输入规模，a为子问题个数，d(n)为分解及综合的代价,39,分治策略与递归算法(续),(1)d(n)=c,实例：二分搜索W(n)=W(n/2)+1a=1,b=2,d(n)=cW(n)=O(logn),40,分治策略与递归算法(续),(2)d(n)=cn,实例：归并排序W(n)=2W(n/2)+n1a=2,b=2,d(n)=O(n),W(n)=O(nlogn),41,实例位乘问题,位乘问题：X,Y为n位二进制数，n=2k,求XY一般方法：W(n)=O(n2)分治法：令X=A2n/2+B,Y=C2n/2+D,则XY=AC2n+(AD+BC)2n/2+BDW(n)=4W(n/2)+cnW(1)=1a=4，b=2,W(n)=O(nlog4)=O(n2)变换：AD+BC=(AB)(DC)+AC+
人人文库> 全部分类> 生活休闲 > 科普知识

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论