算法导论课后习题解析 第三章

时间:2022-01-10 12:08:30

算法导论课后习题解析 第三章

3.1-1
分情况讨论
f(n)g(n) f(n)≥g(n)时, max(f(n),g(n))=f(n) max(f(n),g(n))=f(n),存在 c1=12,c2=1,n0>0 c1=12,c2=1,n0>0使得

0<c1(f(n)+g(n))f(n)c2(f(n)+g(n))nn0 0<c1(f(n)+g(n))≤f(n)≤c2(f(n)+g(n))对于所有n≥n0同理可证当 g(n)>f(n) g(n)>f(n)的情况


3.1-2
(n+a)b=nb+c1nb1+c2nb2++ab=θ(nb) (n+a)b=nb+c1nb−1+c2nb−2+⋯+ab=θ(nb)


3.1-3
大O表示法用来表示一个算法复杂度的上界,而“至少”一词用来形容下界,所以这句话的意思是该算法复杂度的上界只要不小于 O(n2) O(n2)即可,相当于没有说明算法的复杂度的界限,没有意义。


3.1-4
2n+1=O(2n) 2n+1=O(2n)
证明:存在 c=2,n0>0 c=2,n0>0使得

02n+1c2nnn0 0≤2n+1≤c2n对于所有n≥n0 22nO(2n) 22n≠O(2n)
证明:假设存在 c,n0 c,n0使得 022nc2nnn02n2nc2n2nc 0≤22n≤c2n对于所有n≥n0⇒2n∗2n≤c2n⇒2n≤c由于不存在常数c使得等式成立,故产生矛盾,得证。


3.1-5
利用定义就可以直接证明


3.1-6
最坏情况下复杂度为 O(g(n)) O(g(n))说明所有情况时间复杂度为 O(g(n)) O(g(n)),最好情况下时间复杂度为 Θ(g(n)) Θ(g(n))说明所有情况时间复杂度为 Ω(g(n)) Ω(g(n)),根据定理3.1得算法时间复杂度为 Θ(g(n)) Θ(g(n))


3.1-7
f(n)=o(g(n)) f(n)=o(g(n))说明对于任意正常数 c,n0 c,n0,对于所有的 nn0 n≥n0都有

0f(n)<cg(n)nn0 0≤f(n)<cg(n)对于所有n≥n0这时假设 f(n)=ω(g(n)) f(n)=ω(g(n)),说明对于任意正常数 c,n0 c,n0,对于所有的 nn0 n≥n0都有 0cg(n)<f(n) 0≤cg(n)<f(n)然而这样的常数c是存在的,故产生矛盾,可得 o(g(n))ω(g(n))=Φ o(g(n))∩ω(g(n))=Φ


3.1-8

Ω(g(m,n))={f(m,n):c,n0,m0使0cg(n,m)f(n,m)nn0mm0} Ω(g(m,n))={f(m,n):存在大于零的常数c,n0,m0使得0≤cg(n,m)≤f(n,m)对于所有n≥n0或m≥m0} Θ(g(m,n))={f(m,n):c1,c2,n0,m0使0c1g(n,m)f(n,m)c2g(n,m)nn0mm0} Θ(g(m,n))={f(m,n):存在大于零的常数c1,c2,n0,m0使得0≤c1g(n,m)≤f(n,m)≤c2g(n,m)对于所有n≥n0或m≥m0}


3.2-1
由于f(n)和g(n)单调递增,所以对于任意 x1<x2 x1<x2,都有

f(x1)<f(x2) f(x1)<f(x2) g(x1)<g(x2) g(x1)<g(x2)所以 f(x1)+g(x1)<f(x2)+g(x2) f(x1)+g(x1)<f(x2)+g(x2) f(g(x1))<f(g(x2)) f(g(x1))<f(g(x2))如果当f(x)和g(x)都非负时显然有 f(x1)g(x1)<f(x2)g(x2) f(x1)∗g(x1)<f(x2)∗g(x2)


3.2-2

lgalogbc=logbclga=lgalgclgb lg⁡alogb⁡c=logb⁡clg⁡a=lg⁡alg⁡clg⁡b lgclogba=logbalgc=lgalgclgb lg⁡clogb⁡a=logb⁡alg⁡c=lg⁡alg⁡clg⁡b alogbc=clogba ⇒alogb⁡c=clogb⁡a


3.2-3
证明 lg(n!)=Θ(nlgn) lg⁡(n!)=Θ(nlg⁡n)

lgn!=i=1nlgi<i=1nlgn=nlgn lg⁡n!=∑i=1nlg⁡i<∑i=1nlg⁡n=nlg⁡n i=1nlgi=i=1n/2[lgi+lg(ni)]=i=1n/2[lgi(ni)]>i=1n/2lgn24=nlgnn=12nlgn ∑i=1nlg⁡i=∑i=1n/2[lg⁡i+lg⁡(n−i)]=∑i=1n/2[lg⁡i(n−i)]>∑i=1n/2lg⁡n24=nlg⁡n−n=12nlg⁡n lg(n!)=Θ(nlgn) ⇒lg⁡(n!)=Θ(nlg⁡n)证明 n!=ω(2n) n!=ω(2n) n>4i(ni)>22 ∵当n>4时,i(n−i)>22 n!=i=1n/2i(ni)>i=1n/222=2n ∴n!=∏i=1n/2i(n−i)>∏i=1n/222=2n n!=ω(2n) ∴n!=ω(2n)证明 n!=o(nn) n!=o(nn) n>1n!=i=1ni<i=1nn=nn ∵当n>1时,n!=∏i=1ni<∏i=1nn=nn n!=o(nn) ∴n!=o(nn)


3.2-4
证明 f(n) f(n)是否多项式有界等价于证明 lgf(n)=O(lgn) lg⁡f(n)=O(lg⁡n),这是因为如果 f(n) f(n)多项式有界,则存在正常数 c,k,n0 c,k,n0使得对于所有的 n>n0 n>n0都有 f(n)<cnk f(n)<cnk,即 lgf(n)<kclgn lg⁡f(n)<kclg⁡n,所以 lgf(n)=Olgn lg⁡f(n)=Olg⁡n,反之亦然。
对于 lgn! ⌈lg⁡n⌉!我们有

lg(lgn!)=Θ(lgnlglgn)=Θ(lgnlglgn)=ω(lgn) lg⁡(⌈lg⁡n⌉!)=Θ(⌈lg⁡n⌉lg⁡⌈lg⁡n⌉)=Θ(lg⁡nlg⁡lg⁡n)=ω(lg⁡n) lgn! ⌈lg⁡n⌉! 非多项式有界

对于  lglgn! ⌈lg⁡lg⁡n⌉! 我们有 lg(lglgn!)=Θ(lglgnlglglgn)=Θ(lglgnlglglgn)=o((lglgn)2)=o(lgn) lg⁡(⌈lg⁡lg⁡n⌉!)=Θ(⌈lg⁡lg⁡n⌉lg⁡⌈lg⁡lg⁡n⌉)=Θ(lg⁡lg⁡nlg⁡lg⁡lg⁡n)=o((lg⁡lg⁡n)2)=o(lg⁡n) lglgn! ⌈lg⁡lg⁡n⌉! 多项式有界


3.2-5

lglgn=lgn1>lglgn,lgn>2 lg∗⁡lg⁡n=lg∗⁡n−1>lg⁡lg∗⁡n,当lg∗⁡n>2时


3.2-6

ϕ2=(1+52)2=3+52=ϕ+1 ϕ2=(1+52)2=3+52=ϕ+1 ϕ^2=(152)2=352=ϕ^+1 ϕ^2=(1−52)2=3−52=ϕ^+1


3.2-7
证明:
当i = 0时,

ϕ0ϕ^05=0=F0 ϕ0−ϕ^05=0=F0当i = 1时, ϕ1ϕ^15=1=F1 ϕ1−ϕ^15=1=F1假设当i = k-1和i = k时都满足公式,则当i = k+1时 Fk+1=Fk+Fk1=(ϕk+ϕk1)(ϕ^k+ϕ^k1)5=ϕk1(ϕ+1)ϕ^k1(ϕ^+1)5=ϕk+1ϕ^k+15 Fk+1=Fk+Fk−1=(ϕk+ϕk−1)−(ϕ^k+ϕ^k−1)5=ϕk−1(ϕ+1)−ϕ^k−1(ϕ^+1)5=ϕk+1−ϕ^k+15


3.2-8
这题要用到性质 g(n)=Θ(f(n))f(n)=Θ(g(n)) g(n)=Θ(f(n))⇔f(n)=Θ(g(n)),所以 klnk=Θ(n)n=Θ(klnk) kln⁡k=Θ(n)⇔n=Θ(kln⁡k), 要证 k=Θ(n/lnn) k=Θ(n/ln⁡n)等价于证 n/lnn=Θ(k) n/ln⁡n=Θ(k),代入条件得

nlnn=Θ(klnkln(klnk))=Θ(klnklnk)=Θ(k) nln⁡n=Θ(kln⁡kln⁡(kln⁡k))=Θ(kln⁡kln⁡k)=Θ(k)


3-1
a.

P(n)=i=0daini=ndi=0dainidndi=0daicnk P(n)=∑i=0daini=nd∑i=0daini−d≤nd∑i=0dai≤cnkb. P(n)=i=0dainindcnd P(n)=∑i=0daini≥nd≥cndc. 由前两问可证。
d. 同a
e. 同b


3-2

A B O O o o Ω Ω ω ω Θ Θ
lgkn lgk⁡n nϵ yes yes no no no
nk nk cn cn no no yes yes no
n n nsinn nsin⁡n no no no no no
2n 2n 2n/2 2n/2 no no yes yes no
nlgc nlg⁡c clgn clg⁡n yes no yes no yes
lg(n!) lg⁡(n!) lg(nn) lg⁡(nn) yes no yes no yes


3-3
a.

22n+1>22n>(n+1)!>n!>en>n2n>2n>(3/2)n>(lgn)lgn=nlglgn>(lgn)! 22n+1>22n>(n+1)!>n!>en>n2n>2n>(3/2)n>(lg⁡n)lg⁡n=nlg⁡lg⁡n>(lg⁡n)! >n3>n2=4lgn>nlgn=lg(n!)>n=2lgn>(2)lgn=n>22lgn>lg2n>lnn >n3>n2=4lg⁡n>nlg⁡n=lg⁡(n!)>n=2lg⁡n>(2)lg⁡n=n>22lg⁡n>lg2⁡n>ln⁡n >lgn>lnlnn>2lgn>lgn=lg(lgn)>lg(lgn)>n1/lgn=2=1 >lg⁡n>ln⁡ln⁡n>2lg∗⁡n>lg∗⁡n=lg∗⁡(lg⁡n)>lg⁡(lg∗⁡n)>n1/lg⁡n=2=1b. 非连续性函数或者震荡函数就能满足要求,比如 f(n)={n,0, 1n>0  1n<0  f(n)={n, −1n>0 0, −1n<0 


3-4
a. 错误,举个反例 n=O(n2) n=O(n2),而 n2O(n) n2≠O(n) 
b. 错误,举个反例 n+n2=O(n2)O(min(n,n2))=O(n) n+n2=O(n2)≠O(min(n,n2))=O(n) 
c. 正确, f(n)=O(g(n)) f(n)=O(g(n))表明存在正常数 c,n0 c,n0对所有 nn0 n≥n0都有 f(n)cg(n) f(n)≤cg(n),所以也有 lgf(n)lg(cg(n)) lg⁡f(n)≤lg⁡(cg(n)),得证
d. 正确, f(n)=O(g(n)) f(n)=O(g(n))表明存在正常数 c,n0 c,n0对所有 nn0 n≥n0都有 f(n)cg(n) f(n)≤cg(n),所以也有 2f(n)2cg(n) 2f(n)≤2cg(n),得证
e. 正确,同理可证。
f. 正确,定义直接证明。
g. 错误,举个反例 2n=Θ(2n)=ω(2n/2) 2n=Θ(2n)=ω(2n/2)
h. 正确, g(n)=o(f(n)) g(n)=o(f(n))表明存在正常数 n0 n0对于任意正常数 c c,对所有 nn0 n≥n0都有 g(n)<f(n) g(n)<f(n),所以对于所有 nn0 n≥n0都有 f(n)+o(f(n)))<f(n)+f(n)=2f(n) f(n)+o(f(n)))<f(n)+f(n)=2f(n),得证。


3-5
a. 只要证明 f(n)=O(g(n)) f(n)=O(g(n))的补集包含于 f(n)=Ω(g(n)) f(n)=Ω∞(g(n))中即可。 f(n)=O(g(n)) f(n)=O(g(n))表示存在正常数 c,n0 c,n0对所有 nn0 n≥n0都有 f(n)cg(n) f(n)≤cg(n),那么他的补集是不存在常数 c,n0 c,n0对所有 nn0 n≥n0都有 f(n)cg(n) f(n)≤cg(n),显然包含于 f(n)=Ω(g(n)) f(n)=Ω∞(g(n))中,因为如果存在正常数c对有限个n的话成立的话,就能找到一个 n0 n0大于有限个n中最大的那个,使得 f(n)cg(n) f(n)≤cg(n)成立。但是如果换成 Ω(g(n)) Ω(g(n))的话,3-3b中的例子就是个反例。
b. 用符号 Ω(f(n)) Ω(f(n))可以保证在n足够大的情况下算法复杂度都不低于 f(n) f(n),即最好的情况下也不低于 f(n) f(n)。而使用符号 Ω(f(n)) Ω∞(f(n))则表示该算法在很多时候复杂度都不低于 f(n) f(n),但在某些比较好的情况下有可能会低于 f(n) f(n)
c. 没有变化?求指教
d.

Ω~(g(n))={f(n):c,k,n0>0nn00cg(n)lgk(n)f(n)} Ω~(g(n))={f(n):∃c,k,n0>0对∀n≥n0有0≤cg(n)lgk⁡(n)≤f(n)} Θ~(g(n))={f(n):c1,c2,k,n0>0nn00c1g(n)lgk(n)f(n)c2g(n)lgk(n)} Θ~(g(n))={f(n):∃c1,c2,k,n0>0对∀n≥n0有0≤c1g(n)lgk⁡(n)≤f(n)≤c2g(n)lgk⁡(n)}定理3.1由定义可知。


3-6
a.  Θ(n) Θ(n)
b.  Θ(lgn) Θ(lg∗⁡n)
c.  Θ(lgn) Θ(lg⁡n)
d.  Θ(lgn) Θ(lg⁡n)
e.  Θ(lglgn) Θ(lg⁡lg⁡n)
f. 
g.  Θ(lglgn) Θ(lg⁡lg⁡n)
h. 不会,求指教