全文预览已结束
下载本文档
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
一、计算函数的上界、下界和准确界,并给出证明:1、指数函数f(n)=52n+n2。解:令n0=0,当n=n0时,有c1=5,g(n)=2n,使得:f(n)52n=c1g(n)所以,f(n)=(g(n))=(2n)。令n0=4,当nn0时,有:c2=6,g(n)=2nf(n)52n+2n62n=c2(g(n)所以,f(n)=O(g(n)=O(2n)。同时,有:c1g(n)f(n)c2(n)所以,f(n)=(2n)。2、 对数函数f(n)=log2n2。因为:log2n2=2lon2n令n0=1,c1=1,c2=3,g(n)=log2n,有:c1g(n)2lon2nc2g(n)所以:log2n2=(log2n)。3、 函数f(n)=log2j因为:log2jlog2n=nlog2n令n0=1,c1=1,g(n)=nlog2n,有:log2jc1g(n)所以,log2j=0(g(n))=O(nlog2n)另一方面,假定n是偶数,log2jlog2=log2=(log2n-1)=(log2n+log2n-2)因此,令n0=4,c2=,g(n)=nlog2n,对所有的nn0,都有:log2jnlog2n=c2g(n)所以,log2j=(g(n)=(nlog2n)同时,有:c2g(n)log2jc1g(n)所以,log2j=(g(n))=(nlog2n)由此,可以证明:log2n!=(nlog2n)。2、 用递推法求解递归方程。1、 汉诺塔的递归方程为:h(n)=2h(n-1)+1h(1)=1解:h(n)=2h(n-1)+1=22h(n-2)+1+1=4h(n-2)+3 =42h(n-3)+1+3=8h(n-3)+7 =82h(n-4)+1+7=16h(n-4)+15 =2n-22hn-(n-1)+1+2n-2-1=2n-1h(1)+2n-1-1 =2n-12、 解如下递归函数:f(n)=nf(n-1)f(0)=1解:f(n)=nf(n-1)=n(n-1)f(n-2)=n(n-2)(n-3)f(n-4) =n(n-2)(n-3)n-(n-1)f(n-n) =n(n-2)(n-3)1f(0) =n!3、 解如下的递归函数:f(n)=nf(n-1)+n!f(0)=0解:f(n)=nf(n-1)+n!=n(n-1)f(n-2)+(n-1)!+n! =n(n-1)f(n-2)+2n!=n(n-1)(n-2)f(n-3)+(n-2)!+2n! =n(n-1)(n-2)f(n-3)+3n!= =n(n-1)(n-2)n-(n-1)f(n-n)+nn! =n!f(0)+nn!=0+nn! =nn!4、解如下的递归方程:f(n)=2f(n-1)+nf(0)=0解:f(n)=2f(n-1)+nf(n)+n+2=2f(n-1)+(n-1)+2=22f(n-2)+(n-2)+2=4f(n-2)+(n-2)+2=42f(n-3)+(n-3)+2=8f(n-3)+(n-3
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 药品记录与数据管理要求培训课件
- 福建省2024八年级数学上册第11章数的开方期末复习课件新版华东师大版
- 水彩梅花课件教学课件
- 糖尿病日宣传活动总结
- 车间事故应急处理
- 剖腹产产后护理超详细
- 好玩的梯子说课稿
- 安全教育在走廊和楼梯上
- 旅游规划品牌授权准则
- 商品砼合同书
- Unit 7 《Chinese festivals》教学设计-优秀教案
- #110kV变电站一次验收规范#
- 2023年江苏省镇江市九年级上学期数学期中考试试卷含答案
- TIMAAMM 001-2023 蒙医病证分类与代码
- 《网络安全导论》
- 基于核心素养的课程建构
- 世界(全球)审计史
- 运动安全与健康知到章节答案智慧树2023年浙江大学
- 全过程跟踪审计和结算审计服务方案技术标投标方案
- 煤矿掘进工培训教案
- 宾客服务经理工作职责
评论
0/150
提交评论