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 解:
算法设计与分析基础课后习题答案(中文版)_工学_高等教育_教育专区。算法设计与分析基础课后习题答案(中文版)Program 算法设计与分析基础中文版答案习题 1.1 5.....
算法设计与分析基础课后... 44页 1下载券算法设计与分...清华大学出版社 课后习题...
算法设计与分析基础习题参考答案_IT/计算机_专业资料。levtin 潘彦译算法教程的详细参考答案。习题1.1 5..证明等式 gcd(m,n)=gcd(n,m mod n)对每一对正...
算法分析与设计课后习题答案Wklv oh frqwdlqv wkh h{huflvhv/ klqwv/ dqg vroxwlrqv iru Fkdswhu 44 ri ...
算法设计与分析习题答案1-6章_理学_高等教育_教育专区。习题 1 1. 图论诞生... 算法设计与分析第二版课... 37页 免费 算法设计与分析基础课后... 41页 ...
算法设计与分析习题答案1-6章_理学_高等教育_教育专区 暂无评价0人阅读0次下载举报文档 算法设计与分析习题答案1-6章_理学_高等教育_教育专区。习题 1 1....
算法设计与分析第二版课后习题解答_理学_高等教育_教育专区。算法设计与分析基础课后练习答案习题 1.1 4.设计一个计算 的算法,n 是任意正整数。除了赋值和比较...
算法设计与分析复习题目及答案_工学_高等教育_教育专区。一。选择题 1、二分...(要求:分别 给出 divide、conquer、combine 这三个阶段所花的时间,并在此基础上...
2013《计算机算法设计与分析》习题及答案_工学_高等教育_教育专区。《计算机算法设计与分析》习题及答案 2013 秋 1 《计算机算法设计与分析》习题及答案 一.选择...
算法设计与分析习题解答_计算机软件及应用_IT/计算机_专业资料 暂无评价0人阅读0次下载举报文档 算法设计与分析习题解答_计算机软件及应用_IT/计算机_专业资料。...
热门文档