http://www.cnblogs.com/Jiajun/archive/2013/05/06/3063574.html
3.1-1
分情况讨论
当
f(n)≥g(n)
时，
max(f(n),g(n))=f(n)
，存在
c1=12,c2=1,n0>0
使得
0<c1(f(n)+g(n))≤f(n)≤c2(f(n)+g(n))对于所有n≥n0
同理可证当
g(n)>f(n)
的情况
3.1-2
(n+a)b=nb+c1nb−1+c2nb−2+⋯+ab=θ(nb)
3.1-3
大O表示法用来表示一个算法复杂度的上界，而“至少”一词用来形容下界，所以这句话的意思是该算法复杂度的上界只要不小于
O(n2)
即可，相当于没有说明算法的复杂度的界限，没有意义。
3.1-4
2n+1=O(2n)
证明：存在
c=2,n0>0
使得
0≤2n+1≤c2n对于所有n≥n0
22n≠O(2n)
证明：假设存在
c,n0
使得
0≤22n≤c2n对于所有n≥n0⇒2n∗2n≤c2n⇒2n≤c
由于不存在常数c使得等式成立，故产生矛盾，得证。
3.1-5
利用定义就可以直接证明
3.1-6
最坏情况下复杂度为
O(g(n))
说明所有情况时间复杂度为
O(g(n))
，最好情况下时间复杂度为
Θ(g(n))
说明所有情况时间复杂度为
Ω(g(n))
，根据定理3.1得算法时间复杂度为
Θ(g(n))
3.1-7
f(n)=o(g(n))
说明对于任意正常数
c,n0
，对于所有的
n≥n0
都有
0≤f(n)<cg(n)对于所有n≥n0
这时假设
f(n)=ω(g(n))
，说明对于任意正常数
c,n0
，对于所有的
n≥n0
都有
0≤cg(n)<f(n)
然而这样的常数c是存在的，故产生矛盾，可得
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):存在大于零的常数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
，都有
f(x1)<f(x2)
g(x1)<g(x2)
所以
f(x1)+g(x1)<f(x2)+g(x2)
f(g(x1))<f(g(x2))
如果当f(x)和g(x)都非负时显然有
f(x1)∗g(x1)<f(x2)∗g(x2)
3.2-2
lgalogbc=logbclga=lgalgclgb
lgclogba=logbalgc=lgalgclgb
⇒alogbc=clogba
3.2-3
证明
lg(n!)=Θ(nlgn)
：
lgn!=∑i=1nlgi<∑i=1nlgn=nlgn
∑i=1nlgi=∑i=1n/2[lgi+lg(n−i)]=∑i=1n/2[lgi(n−i)]>∑i=1n/2lgn24=nlgn−n=12nlgn
⇒lg(n!)=Θ(nlgn)
证明
n!=ω(2n)
：
∵当n>4时，i(n−i)>22
∴n!=∏i=1n/2i(n−i)>∏i=1n/222=2n
∴n!=ω(2n)
证明
n!=o(nn)
：
∵当n>1时，n!=∏i=1ni<∏i=1nn=nn
∴n!=o(nn)
3.2-4
证明
f(n)
是否多项式有界等价于证明
lgf(n)=O(lgn)
，这是因为如果
f(n)
多项式有界，则存在正常数
c,k,n0
使得对于所有的
n>n0
都有
f(n)<cnk
，即
lgf(n)<kclgn
，所以
lgf(n)=Olgn
，反之亦然。
对于
⌈lgn⌉!
我们有
lg(⌈lgn⌉!)=Θ(⌈lgn⌉lg⌈lgn⌉)=Θ(lgnlglgn)=ω(lgn)
⌈lgn⌉!
非多项式有界
对于
⌈lglgn⌉!
我们有
lg(⌈lglgn⌉!)=Θ(⌈lglgn⌉lg⌈lglgn⌉)=Θ(lglgnlglglgn)=o((lglgn)2)=o(lgn)
⌈lglgn⌉!
多项式有界
3.2-5
lg∗lgn=lg∗n−1>lglg∗n,当lg∗n>2时
3.2-6
ϕ2=(1+5√2)2=3+5√2=ϕ+1
ϕ^2=(1−5√2)2=3−5√2=ϕ^+1
3.2-7
证明：
当i = 0时，
ϕ0−ϕ^05√=0=F0
当i = 1时，
ϕ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√
3.2-8
这题要用到性质
g(n)=Θ(f(n))⇔f(n)=Θ(g(n))
，所以
klnk=Θ(n)⇔n=Θ(klnk)
， 要证
k=Θ(n/lnn)
等价于证
n/lnn=Θ(k)
，代入条件得
nlnn=Θ(klnkln(klnk))=Θ(klnklnk)=Θ(k)
