文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > 高等教育 > 工学 > 算法设计与分析基础课后习题答案(中文版)
侵权投诉

算法设计与分析基础课后习题答案(中文版)

f(n)

c

g(n) c1 g(n) for all n>=n0,c1=c/α>0

即:f(n)∈Θ(αg(n))

8.证明本节定理对于下列符号也成立: a.Ω符号 b.Θ符号 证明:

a。we need to proof that if t1(n)∈Ω(g1(n)) and t2(n)∈Ω(g2(n)), then t1(n)+ t2(n)∈Ω(max{g1(n), g2(n)})。

由 t1(n)∈Ω(g1(n)),

t1(n)≥c1g1(n) for all n>=n1, where c1>0 由 t2(n)∈Ω(g2(n)),

T2(n)≥c2g2(n) for all n>=n2, where c2>0 那么,取c>=min{c1,c2},当n>=max{n1,n2}时: t1(n)+ t2(n)≥c1g1(n)+ c2g2(n) ≥c g1(n)+c g2(n)≥c[g1(n)+ g2(n)] ≥cmax{ g1(n), g2(n)} 所以以命题成立。

b. t1(n)+t2(n) ∈Θ(max(g1(n),g2(n)))

证明:由大 的定义知,必须确定常数c1、c2和n0,使得对于所有n>=n0,有:

c1max((g1(n),g2(n)) t1(n) t2(n) max(g1(n),g2(n))

由t1(n)∈Θ(g1(n))知,存在非负整数a1,a2和n1使: a1*g1(n)<=t1(n)<=a2*g1(n)-----(1)

由t2(n)∈Θ(g2(n))知,存在非负整数b1,b2和n2使: b1*g2(n)<=t2(n)<=b2*g2(n)-----(2) (1)+(2):

a1*g1(n)+ b1*g2(n)<=t1(n)+t2(n) <= a2*g1(n)+ b2*g2(n) 令c1=min(a1,b1),c2=max(a2,b2),则

C1*(g1+g2)<= t1(n)+t2(n) <=c2(g1+g2)-----(3) 不失一般性假设max(g1(n),g2(n))=g1(n).

显然,g1(n)+g2(n)<2g1(n),即g1+g2<2max(g1,g2)

又g2(n)>0,g1(n)+g2(n)>g1(n),即g1+g2>max(g1,g2)。 则(3)式转换为:

C1*max(g1,g2) <= t1(n)+t2(n) <=c2*2max(g1,g2) 所以当c1=min(a1,b1),c2=2c2=2max(c1,c2),n0=max(n1,n2)时,当n>=n0时上述不等式成立。 证毕。

习题2.4

1. 解下列递推关系 (做a,b) a.

x(n) x(n 1) 5当n>1时

x(1) 0 解:

上一页第5页

你可能喜欢

  • 计算机算法设计与分析
  • 中南大学
  • C语言经典算法
  • C语言谭浩强
  • 排序算法总结
  • C语言函数
  • C语言源代码
  • 语言分析

热门文档

相关文档

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email