第三章 函数的增长
渐进记号
- Θ -- 上界和下界，紧确界，相当于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
答：
- 2^(n+1) = 2 * 2^n = O(2^n)，成立
- 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
答：若函数f(n)有多项式边界，则满足lg f(n) = o(lg n)。
3.2-5 ~8
答：
- 第二个大。lg*n表示使n < 1所需取对数的次数。
- 代入式中可验证。
- 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 - 由Θ的自反性有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,多项式成立，指数函数不成立。
