本文共 1586 字，大约阅读时间需要 5 分钟。

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

3-1
a.

3-2

3-3
a.

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.

3-6
a.  Θ(n)
b.  Θ(lg∗n)
c.  Θ(lgn)
d.  Θ(lgn)
e.  Θ(lglgn)
f.  ∞
g.  Θ(lglgn)
h. 不会，求指教