算法導論（第三版） 第三章思考題

http://www.cnblogs.com/Jiajun/archive/2013/05/06/3063574.html

3-1

a.

P(n)=∑i=0daini=nd∑i=0daini−d≤nd∑i=0dai≤cnk b. P(n)=∑i=0daini≥nd≥cnd c. 由前兩問可證。

d. 同a

e. 同b

3-2

A	B	O	o	Ω	ω	Θ
lgkn	nϵ	yes	yes	no	no	no
nk	cn	no	no	yes	yes	no
n√	nsinn	no	no	no	no	no
2n	2n/2	no	no	yes	yes	no
nlgc	clgn	yes	no	yes	no	yes
lg(n!)	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)! >n3>n2=4lgn>nlgn=lg(n!)>n=2lgn>(2√)lgn=n√>22lgn√>lg2n>lnn >lgn−−−√>lnlnn>2lg∗n>lg∗n=lg∗(lgn)>lg(lg∗n)>n1/lgn=2=1 b. 非連續性函數或者震蕩函數就能滿足要求，比如 f(n)={n,0, −1n>0  −1n<0 

3-4

a. 錯誤，舉個反例 n=O(n2) ，而 n2≠O(n)  

b. 錯誤，舉個反例 n+n2=O(n2)≠O(min(n,n2))=O(n)  

c. 正确， f(n)=O(g(n)) 表明存在正常數 c,n0 對所有 n≥n0 都有 f(n)≤cg(n) ，是以也有 lgf(n)≤lg(cg(n)) ，得證

d. 正确， f(n)=O(g(n)) 表明存在正常數 c,n0 對所有 n≥n0 都有 f(n)≤cg(n) ，是以也有 2f(n)≤2cg(n) ，得證

e. 正确，同理可證。

f. 正确，定義直接證明。

g. 錯誤，舉個反例 2n=Θ(2n)=ω(2n/2)

h. 正确， g(n)=o(f(n)) 表明存在正常數 n0 對于任意正常數 c ，對所有 n≥n0 都有 g(n)<f(n) ，是以對于所有 n≥n0 都有 f(n)+o(f(n)))<f(n)+f(n)=2f(n) ，得證。

3-5

a. 隻要證明 f(n)=O(g(n)) 的補集包含于 f(n)=Ω∞(g(n)) 中即可。 f(n)=O(g(n)) 表示存在正常數 c,n0 對所有 n≥n0 都有 f(n)≤cg(n) ，那麼他的補集是不存在常數 c,n0 對所有 n≥n0 都有 f(n)≤cg(n) ，顯然包含于 f(n)=Ω∞(g(n)) 中，因為如果存在正常數c對有限個n的話成立的話，就能找到一個 n0 大于有限個n中最大的那個，使得 f(n)≤cg(n) 成立。但是如果換成 Ω(g(n)) 的話，3-3b中的例子就是個反例。

b. 用符号 Ω(f(n)) 可以保證在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):∃c1,c2,k,n0>0對∀n≥n0有0≤c1g(n)lgk(n)≤f(n)≤c2g(n)lgk(n)} 定理3.1由定義可知。

3-6

a.  Θ(n)

b.  Θ(lg∗n)

c.  Θ(lgn)

d.  Θ(lgn)

e.  Θ(lglgn)

f.  ∞

g.  Θ(lglgn)

h. 不會，求指教