算法分析与设计 第1章习题答案 1-1,1-2,1-3,1-6

第一章习题（1-1,1-2,1-3,1-6）

1-1 求下列函数的渐进表达式

3n+10n = O(n) 2nnn/10+2 = O(2) 21+1/n = O(1)

3

logn = O(logn)

n

10log3 = O(n) 知识点：

如果存在正的常数C和自然数N0，使得：

当N>=N0时有f(N)<=Cg(N)，则称f(N)当N充分大时上有界，且g(N)是它的一个上界，记为f(N)=O(g(N)).

这时，可以说f(N)的阶不高于g(N)的阶。

1-2 论O(1)和O(2)的区别

O(1)和O(2)差别仅在于其中的常数因子，根据渐进上界记号O的定义可知，O(1)=O(2)。

2

2

1-3 从低到高排列以下表达式（按渐进阶排列以下表达式）

结果：2 logn n 20n 4n 3 n! 分析：

2/3

当n>=1时，有logn< n

n

当n>=7时，有3< n! 补充：

1/3

当n>=4时，有logn> n 1-6 对于下列各组函数f(n)和g(n)，确定f(n)=O(g(n))或f(n)=?(g(n))或f(n)=?(g(n))。

知识点：

f(n)的阶不高于g(n)的阶：f(n)=O(g(n))； f(n)的阶不低于g(n)的阶：f(n)=?(g(n))； f(n)与g(n) 同阶：f(n)=?(g(n))

2/32n

(1) f(n)= logn ; g(n)= logn+5

f(n)与g(n)同阶，故f(n)=?(g(n))

21/2

(2) f(n)= logn ; g(n)= n 当n>=8时，f(n)<=g(n)，故f(n)=O(g(n))

2

分析：此类题目不易直接看出阶的高低，可用几个数字代入观察结果。

1236810

如依次用n=1, 2, 2, 2, 2, 2, 2

2

(3) f(n)= n ; g(n)= logn

f(n)=?(g(n))

(4) f(n)= nlogn+n; g(n)= logn

f(n)=?(g(n))

(5) f(n)= 10 ; g(n)= log10 f(n)=?(g(n))

2

(6) f(n)= logn ; g(n)= logn

f(n)=?(g(n)) n2

(7) f(n)= 2 ; g(n)= 100 n

f(n)=?(g(n)) nn

(8) f(n)= 2 ; g(n)= 3

f(n)=O(g(n))