会员注册| 登录| QQ登录 微博登录 帮助中心 睿知网_睿知网
搜索

热门搜索: 大学 教程2 综合 新标准 英语 课后

计算机算法设计与分析(第4版)-王晓东习题解答计算机算法设计与分析(第4版)-王晓东习题解答 -- 1 元

宽屏显示 收藏 分享

广告剩余:

编号: 228   大小: 0.46 MB   格式: pdf   上传时间: 2018-03-07 16:49
   【编辑】
1
关 键 词:
分析 设计 计算机 算法
文档简介:
第一章 1. 证明下列Ο 、Ω 和Θ 的性质 1) f=Ο (g)当且仅当 g=Ω (f)

作业

证明:充分性。若 f=Ο (g),则必然存在常数 c1>0 和 n0,使得nn0,有 f c1*g(n)。由于 c10,故 g(n)  1/ c1 *f(n),故 g=Ω (f)。 必要性。同理,若 g=Ω (f),则必然存在 c2>0 和 n0,使得nn0,有 g(n)  c2 *f(n).由于 c20,故 f(n)  1/ c2*f(n),故 f=Ο (g)。

2)

若 f=Θ (g)则 g=Θ (f)

证明: f=Θ (g), 若 则必然存在常数 c1>0, 2>0 和 n0, c 使得nn0, c1*g(n) 有 f(n)  c2*g(n)。由于 c10,c20,f(n) c1*g(n)可得 g(n)  1/c1*f(n),同时, f(n) c2*g(n), g(n)  1/c2*f(n), 1/c2*f(n) g(n)  1/c1*f(n), g=Θ (f)。 有 即 故

3)

Ο (f+g)= Ο (max(f,g)),对于Ω 和Θ 同样成立。

证明:设 F(n)= Ο (f+g),则存在 c1>0,和 n1,使得nn1,有 F(n)  c1 (f(n)+g(n)) = c1 f(n) + c1g(n)  c1*max{f,g}+ c1*max{f,g} =2 c1*max{f,g} 所以,F(n)= Ο (max(f,g)),即Ο (f+g)= Ο (max(f,g)) 对于Ω 和Θ 同理证明可以成立。

4)

log(n!)= Θ(nlogn)
1

证明: 由于 log(n!)=  log i   log n =nlogn,所以可得 log(n!)= Ο (nlogn)。
i 1 i 1 n n

由于对所有的偶数 n 有, log(n!)=  log i   log i   log n / 2 (n/2)log(n/2)=(nlogn)/2-n/2。
i 1 i n / 2 i n / 2 n n n

当 n4, (nlogn)/2-n/2(nlogn)/4, 故可得n4, log(n!) (nlogn)/4, log(n!)= 即 Ω (nlogn)。 综合以上两点可得 log(n!)= Θ(nlogn)

2. 设计一个算法,求给定 n 个元素的第二大元素,并给出算法在最坏情况 下使用的比较次数。 (复杂度至多为 2n-3) 算法: Void findsecond(ElemType A[]) { for (i=2; i
温馨提示:
1: 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
2: 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
3.本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
5. 睿知网仅提供交流平台,并不能对任何下载内容负责。
6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
  睿知网所有资源均是用户自行上传分享,仅供网友学习交流,未经上传用户书面授权,请勿作他用。
评论列表(网友评论仅供网友表达个人看法,并不表明本站同意其观点或证实其描述)

当前资源信息

0.0


浏览:
这就是爱上传于2018-03-07 16:49

官方联系方式

客服手机:17606998714   
2:不支持迅雷下载,请使用浏览器下载   
3:不支持QQ浏览器下载,请用其他浏览器   
4:下载后的文档和图纸-无水印   
5:文档经过压缩,下载后原文更清晰   

相关搜索

广告位
广告位
Copyright © 2012-2018 睿知网 版权所有
滇ICP备18000065号-1