渐进记号

• Θ -- 上界和下界，紧确界，相当于f(n) ∈ [c1 * g(n), c2 * g(n)]
• Ω -- 闭区间下界，最好运行时间，相当于 f(n) ∈ [c * g(n), ∞)
• Ο -- 闭区间上界，最差运行时间，相当于 f(n) ∈ [0, c * g(n)]
• ω -- 开区间下界，最好运行时间，相当于 f(n) ∈ (c * g(n), ∞)

• ο -- 开区间上界，最差运行时间，相当于 f(n) ∈ [0, c * g(n))

  
  

不是所有函数都可渐进比较，对于f(n) 和g(n)可能 f(n) = O（g(n)）与 f(n) = Ω （g(n)）都不成立。

练习

3.1-1

答：要证c1(f(n) + g(n)) <= max(f(n), g(n)) <= c2(f(n) + g(n))，令c1 = 0.5, c2 = 1。

3.1-2

当 n 很大时只有第一项是主要部分。

3.1-3

答：O(n^2)是用来说明上界的，最小的上界没有意义。

3.1-4

答：

1. 2^(n+1) = 2 * 2^n = O(2^n)，成立
2. 2^2n = 2^n * 2^n，不成立

3.1-5

答：

• 充分性：因为f(n)=Θ(g(n))，由定义有存在c1、c2和n0（其中n>=n0）使得0<=c1g(n)<=f(n)<=c2g(n)。于是：
  存在c1和n0（其中n>=n0）使得0<=c1g(n)<=f(n)，即f(n)=Ω(g(n))
  存在c2和n0（其中n>=n0）使得0<=f(n)<=c2g(n)，即f(n)=O(g(n))

• 必要性：f(n)=Ω(g(n)) => “存在c1'和n1（其中n>=n1）使得0<=c1'g(n)<=f(n)”。
  f(n)=O(g(n)) => “存在c2'和n2（其中n>=n2）使得0<=f(n)<=c2'g(n)”。
  令c1=c1'，c2=c2'，n0=max{n1, n2}，由Θ的定义有：f(n) = Θ(g(n))。

3.1-6

答：由上一题可知。

3.1-7

答：用反证法，假设o(g(n)) ∩ ω(g(n))不是空集，则对于所有的c1,c2>0有0<=c1g(n)<f(n)<c2g(n)其中n>=max(n1, n2)。令c1=c2，就得出矛盾，所以o(g(n)) ∩ ω(g(n))是空集。

3.1-8

答：同样的，将题干例子改不等式方向得到Ω(g(n,m))，两边同时加约束得到Θ(g(n, m))。

第二节主要是数学知识。包括单调性、取整、模运算、多项式、指数、对数、阶乘、复合函数、菲波那切数列等，结合附录复习。

练习

3.2-1

3.2-2

证明 a^logb(c) = c^ logb(a)
答：

3.2-3

证明：lg(n!) = Θ(nlgn)，n! = ω(2^n) 和 n! = o(n^n)
答：

• 上界：lg(n!) < lg(n^n) = nlgn
• 下界：根据斯特林近似公式有
  n! = √(2πn) (n/e)^n (1 + Θ(1/n))
  lg(n!) = lg√(2πn) + nlg(n/e) + lg(1+Θ(1/n))
  = (1/2)lg(2πn) + n(lgn - lge) + lg(1+c/n))
  = Θ(lgn) + Θ(nlgn) + lg(n+c) - lgn
  = Θ(nlgn)

3.2-4

3.2-5 ~8

答：

5. 第二个大。lg*n表示使n < 1所需取对数的次数。
6. 代入式中可验证。
7. F[0] = 0，F[1] = 1。假设
   F[i-1] = (φ^(i-1) - φ'^(i-1)) / √5
   F[i-2] = (φ^(i-2) - φ'^(i-2)) / √5
   则F[i] = F[i-1] + F[i-2]
   = (φ^(i-1) + φ^(i-2) - φ'^(i-1) - φ'^(i-2)) / √5
   = (φ^(i-2)(φ + 1) - φ'^(i-2)(φ' + 1)) / √5
   整理有
   φ + 1 = (3 + √5) / 2
   φ^2 = (1 + 2√5 + 5) / 4 = (3 + √5) / 2
   φ + 1 = φ^2
   同理 φ'+ 1 = φ'^2。代入后，得到
   F[i] = (φ^i - φ'^i) / √5
8. 由Θ的自反性有n = Θ(k*lnk)
   ∴n/lnn = Θ[k/lnk * ln(k/lnk)]
   = Θ[k - k/ln^2(k)]
   = Θ(k)

思考题

3-1

当总结

3-2

3-3

总体：指数的指数 > 阶乘 > 指数函数 > 幂函数 > 对数函数 > 多重对数 > 常数。

3-4

a. f
b. f
c. t
d. f, 缺约束条件
e. f, 缺约束条件，f(n)可能 < 1
f. t
g. f,多项式成立，指数函数不成立。

3-5

3-6

参考：算法导论题解