算法导论（第三版） 第三章思考题

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. 不会，求指教