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

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

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))对于所有n≥n0 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+c1nb−1+c2nb−2+⋯+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使得

0≤2n+1≤c2n对于所有n≥n0 0≤2n+1≤c2n对于所有n≥n0 22n≠O(2n) 22n≠O(2n)
证明：假设存在 c,n0 c,n0使得 0≤22n≤c2n对于所有n≥n0⇒2n∗2n≤c2n⇒2n≤c 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，对于所有的 n≥n0 n≥n0都有

0≤f(n)<cg(n)对于所有n≥n0 0≤f(n)<cg(n)对于所有n≥n0这时假设 f(n)=ω(g(n)) f(n)=ω(g(n))，说明对于任意正常数 c,n0 c,n0，对于所有的 n≥n0 n≥n0都有 0≤cg(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使得0≤cg(n,m)≤f(n,m)对于所有n≥n0或m≥m0} Ω(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使得0≤c1g(n,m)≤f(n,m)≤c2g(n,m)对于所有n≥n0或m≥m0} Θ(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(n−i)]=∑i=1n/2[lgi(n−i)]>∑i=1n/2lgn24=nlgn−n=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>4时，i(n−i)>22 ∵当n>4时，i(n−i)>22 ∴n!=∏i=1n/2i(n−i)>∏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>1时，n!=∏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⌉!)=Θ(⌈lgn⌉lg⌈lgn⌉)=Θ(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⌉!)=Θ(⌈lglgn⌉lg⌈lglgn⌉)=Θ(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

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

3.2-6

ϕ2=(1+5√2)2=3+5√2=ϕ+1 ϕ2=(1+52)2=3+52=ϕ+1 ϕ^2=(1−5√2)2=3−5√2=ϕ^+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+Fk−1=(ϕk+ϕk−1)−(ϕ^k+ϕ^k−1)5√=ϕk−1(ϕ+1)−ϕ^k−1(ϕ^+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=nd∑i=0daini−d≤nd∑i=0dai≤cnk P(n)=∑i=0daini=nd∑i=0daini−d≤nd∑i=0dai≤cnkb. P(n)=∑i=0daini≥nd≥cnd P(n)=∑i=0daini≥nd≥cndc. 由前两问可证。
d. 同a
e. 同b

3-2

A	B	O O	o o	Ω Ω	ω ω	Θ Θ
lgkn lgk⁡n	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>2lg∗n>lg∗n=lg∗(lgn)>lg(lg∗n)>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)，而 n2≠O(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对所有 n≥n0 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对所有 n≥n0 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，对所有 n≥n0 n≥n0都有 g(n)<f(n) g(n)<f(n)，所以对于所有 n≥n0 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对所有 n≥n0 n≥n0都有 f(n)≤cg(n) f(n)≤cg(n)，那么他的补集是不存在常数 c,n0 c,n0对所有 n≥n0 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>0对∀n≥n0有0≤cg(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>0对∀n≥n0有0≤c1g(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.  Θ(lg∗n) Θ(lg∗⁡n)
c.  Θ(lgn) Θ(lg⁡n)
d.  Θ(lgn) Θ(lg⁡n)
e.  Θ(lglgn) Θ(lg⁡lg⁡n)
f.  ∞ ∞
g.  Θ(lglgn) Θ(lg⁡lg⁡n)
h. 不会，求指教