注：由于本章主要是数学知识，要求一定的高等数学基础，且习题大多数为证明题（输入有一定困难。。），因此本章答案主要以证明思路为主。

3.1 渐近记号

3.1-1

思路：首先仿照Θ记号的基本定义表出本题的定义，然后取c1和c2分别为1/2和1即可证明。

3.1-2

思路：对n+a和n+|a|的大小关系进行分类，可证明出当n足够大时，n/2≤n+a≤2n，之后取c1和c2分别为2-b和2b,n0=2|a|即可证明。

3.1-3

思路：极端地，因为0也是O(n2)而运行时间肯定为正，所以从这一表述出无法得到运行时间的任何信息。

3.1-4

解：成立；不成立。

3.1-5

思路：必要性（仅当）易证，充分性（当）可使用这三种符号的定义来证明。

3.1-6

思路：使用3.1-5得出的定理3.1可证明。

3.1-7

思路：使用定义，易证。

3.1-8

照葫芦画瓢，略略略。

3.2 标准记号与常用函数

3.2-1

常见于高中到大学各练习，略。

3.2-2

思路：两边同时取以a为底的对数。

3.2-3

思路：使用斯特林（Stirling）近似公式证明定理（3.19）。后面两式易证。

3.2-4

首先，结论是前者不是多项式有界，而后者是。

证明：

若f(n)多项式有界，则存在c, k ,n0

使得n≥n0时，f(n)≤cnk

因此，lg(f(n))≤kclgn，意味着lg(f(n))=O(lgn)

同样地，若lg(f(n))=O(lgn)，则f(n)多项式有界

⌈lgn⌉=Θ(lgn)

lg(⌈lgn⌉!)=Θ(lgn·lglgn)=ω(lgn)

⌈lglgn⌉=Θ(lglgn)

lg(⌈lglgn⌉!)=Θ(lglgn·lglglgn)=o((lglgn)2)=o(lg2(lgn))=o(lgn)

3.2-5

解：lg*(lgn)

3.2-6

思路：代入

3.2-7

易证。

3.2-8

证明：

n=Θ(klgk)

lgn=Θ(lgk+lglgk)=Θ(lgk)

lnn=Θ(lnk)

klnk/lnk=Θ(n/lnk)=Θ(n/lnn)

思考题

3-1 （多项式的渐近行为）

易证。

3-2 （相对渐近增长）

a.

是是否否否

b.

是是是否否

c.

否否否否否

d.

否否是是否

e.

是否是否是

f.

是否是否是

3-3 （根据渐近增长率排序）

a.

注：以下每一行代表一等价类。

C0: 22n+1

C1: 22n

C2: (n+1)!

C3: n!

C4: en

C5: n·2n

C6: 2n

C7: (3/2)n

C8: nlglgn、(lgn)lgn

C9: (lgn)!

C10: n3

C11: n2、4lgn

C12: nlgn、lg(n!)

C13: n、2lgn

C14: (√2)lgn

C15: 2√(2lgn)

C16: lg2n

C17: lnn

C18: √(lgn)

C19: lnlnn

C20: 2lg*n

C21: lg*n、lg*(lgn)

C22: lg(lg*n)

C23: 1、n1/lgn

b.

(22n+1)sinn

3-4 （渐近记号的性质）

a.

错误，n=O(n2)，但反之不然

b.

错误，n2+n=Θ(n2)≠Θ(min(n2, n))=Θ(n)

c.

正确

d.

错误，n=O(2n)，但2n≠Θ(22n)=Θ(4n)

e.

错误，1/n2≠O(1/n4)

f.

正确

g.

错误，类似d

h.

正确

3-5 （O与Ω的一些变形）

这题还是不明白除了数学之外的意义在哪。。

a.

本题证明翻译自/03/problems/05.html

只需要看cg(n)≤f(n)是对有限还是无限的整数成立。如果无限，则有Ω∞；如果有限，则设最大的一个为n0，那么当n>n0时，O成立。

换成Ω不成立，因为有类似nsinn的函数。

b.

优点：扩充了Ω符号的范围。使得Ω∞符号与O符号涵盖所有的渐近非负的函数关系？？

缺点：似乎扩充了也没有什么实际用处？？

c.

“当且仅当”变为“仅当”，因为弱化了条件？

d.

定义可依样，略；若同时使用软O软Ω软Θ，则“当且仅当”成立？

3-6 （多重函数）

a.

Θ(n)

b.

Θ(lg*n)

c.

Θ(lgn)

d.

Θ(lgn)

e.

Θ(lglgn)

f.

无法收敛

g.

Θ(log3lgn)

h.

ω(lglgn), o(lgn)