本文共 2128 字，大约阅读时间需要 7 分钟。
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 使得
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 都有
这时假设 f(n)=ω(g(n)) ，说明对于任意正常数 c,n0 ，对于所有的 n≥n0 都有 然而这样的常数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(x)和g(x)都非负时显然有
3.2-2
lgalogbc=logbclga=lgalgclgb lgclogba=logbalgc=lgalgclgb
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 证明 n!=ω(2n) ： ∴n!=∏i=1n/2i(n−i)>∏i=1n/222=2n 证明 n!=o(nn) ： ∵当n>1时，n!=∏i=1ni<∏i=1nn=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
3.2-7
证明：
当i = 0时，
当i = 1时， 假设当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)