『算法导论』第 3 章:函数的增长

主要内容

本章讲解如何简化算法的渐近分析,介绍了几类渐近记号。最后简单介绍了常用函数的性质。本章的内容在这里描述得非常简略,但为了保持整个系列的完整性,还是贴出来了。

渐近记号

本章介绍了如下渐近记号,它们的严格定义分别如下:

  1. 若$f(n) = \Theta(g(n))$,则存在正常量$c_1$、$c_2$和$n_0$,使得对所有$n \ge n_0$,有$0 \le c_1 g(n) \le f(n) \le c_2 g(n)$
  2. 若$f(n) = O(g(n))$,则存在正常量$c$和$n_0$,使得对所有$n \ge n_0$,有$0 \le f(n) \le c g(n)$
  3. 若$f(n) = \Omega(g(n))$,则存在正常量$c$和$n_0$,使得对所有$n \ge n_0$,有$0 \le c g(n) \le f(n)$
  4. 若$f(n) = o(g(n))$,则对任意$c>0$,存在常量$n_0>0$,使得对所有$n \ge n_0$,有$0 \le f(n) < c g(n)$
  5. 若$f(n) = \omega(g(n))$,则对任意$c>0$,存在常量$n_0>0$,使得对所有$n \ge n_0$,有$0 \le c g(n) < f(n)$

为了更形象地理解本节介绍的几种渐近记号,可以在两个函数的渐近比较和两个实数的比较之间做一种类比:

  • $f(n) = O(g(n))$类似于$a \le b$
  • $f(n) = \Omega(g(n))$类似于$a \ge b$
  • $f(n) = \Theta(g(n))$类似于$a = b$
  • $f(n) = o(g(n))$类似于$a < b$
  • $f(n) = \omega(g(n))$类似于$a > b$

标准记号与常用函数

本节主要讲解了常用的数学函数和记号,涉及到高中数学和基础微积分的知识。

习题解答

练习题

3.1-1 解答:即需证明存在正常数$c_1$,$c_2$和$n_0$,使得当$n \ge n_0$时有:

$$ c_1(f(n)+g(n)) \le \max(f(n), g(n)) \le c_2(f(n)+g(n)) $$

由于$f(n)$和$g(n)$均是渐近非负函数,所以存在$n_0$,使得当$n \ge n_0$时,有$f(n) \ge 0$和$g(n) \ge 0$。令

$$ h(x) = \max(f(n), g(n))$$

$$ 0 \le f(n) \le h(n) \\
0 \le g(n) \le h(n) $$

所以有

$$ 0 \le f(n)+g(n) \le 2h(n) \\
0 \le (f(n)+g(n))/2 \le h(n) $$

又有

$$ h(n) \le f(n)+g(n) $$

所以存在$c_1 = 1/2$,$c_2 = 1$和$n_0 \ge 0$满足条件,得证。

3.1-2 解答:即需证明存在正常数$c_1$,$c_2$和$n_0$,使得当$n \ge n_0$时有:

$$ c_1 n^b \le (n+a)^b \le c_2 n^b $$

$$ c_1 \le (1+a/n)^b \le c_2 $$

当$b > 0$时,幂函数在$[0, +\infty)$上单调递增。下面根据$a$的符号分情况讨论:

  1. 当$a > 0$时,令$n \ge n_0 = a$,则有$1 \le 1+a/n \le 2$,即$c_1 = 1, c_2 = 2$,根据幂函数的单调性,上式成立;
  2. 当$a < 0$时,$1+a/n = 1-|a|/n$,令$n \ge n_0 = 2|a|$,则有$1/2 \le (1-|a|/n) \le 1$,即$c_1 = 1/2, c_2 = 1$,根据幂函数的单调性,上式成立。

所以得证。

3.1-3 解答:因为$O$符号没有提供一个下界。

3.1-4 解答:$2^{n+1} = O(2^n)$成立,$2^{2n} = O(2^n)$不成立。

3.1-5 解答:要证明的公式是:

$$ \lim_{n \to \infty}f(n)/g(n) = 0 $$

根据数列极限的$\epsilon-N$定义,对任意$\epsilon > 0$,存在自然数$N$使得当$n > N$时,有$|f(n)/g(n)| < \epsilon$。

根据$f(n) = o(g(n))$的定义,对任意正常量$c > 0$,存在$n_0 > 0$,使得对所有$n \ge n_0$,有$0 \le f(n) < cg(n)$,即$|f(n)/g(n)| < c$,取$\epsilon = c$,$N = n_0$,得证。

3.1-6 解答:$O$记号提供了一个渐近上界,$\Omega$记号提供了渐近下界,所以为$\Theta(g(n))$。严格证明略。

3.1-7 解答:类似于$a < b$和$a > b$不可能同时成立。

3.1-8 解答:如下:

$f(n, m) = \Omega(g(n, m))$,则存在正常量$c$, $n_0$和$m_0$,使得对所有的$n \ge n_0$或$m \ge m_0$,有$0 \le cg(n, m) \le f(n, m)$.
$f(n, m) = \Theta(g(n, m))$,则存在正常量$c_1$,$c_2$,$n_0$和$m_0$,使得对所有的$n \ge n_0$或$m \ge m_0$,有 $c_1 g(n, m) \le f(n, m) \le c_2 g(n, m)$.

3.2-1 解答:按照单调性的定义即可证明,略。

3.2-2 解答:由公式$a = b^{\log_b a}$得:

$$
a^{\log_b c} = (b^{\log_b a})^{\log_b c} = b^{\log_b a \log_b c} \\
c^{\log_b a} = (b^{\log_b c})^{\log_b a} = b^{\log_b c \log_b a}
$$

得证。

3.2-3 解答:要证明的(3.19)式为$n! = \Theta(n \lg n)$,借助斯特林近似公式,证明如下:

$$
\lg(n!) = \lg \sqrt{2 \pi n} + \lg (n/e)^n + \lg (1+\Theta(1/n)) = \Theta(\lg n) + \Theta(n \lg n) = \Theta(n \lg n)
$$

要证明$n! = o(n^n)$,证明$\lim_{n \to \infty}n!/n^n = 0$即可,代入斯特林近似公式即得证。

要证明$n! = \omega(2^n)$,证明$\lim_{n \to \infty}n!/2^n = \infty$即可。令$h(n) = n!/2^n$,则:

$$h(n) = \frac{n!}{2^n} = \frac{(n-1)!}{2^{n-1}} \frac{n}{2} = h(n-1) \frac{n}{2}$$

当$n=4$时,$h(n)>1$,当$n>4$时,$n/2 > 2$,所以$h(n) > 2^{n-4}$,所以$h(n)$的极限为$\infty$。

3.2-4 解答:星号题,略。

3.2-5 解答:星号题,略。

3.2-6 解答:根据黄金分割率的定义有:$\phi / 1 = \phi / (1 - \phi)$,即满足方程$x^2 = x + 1$,得证。

3.2-7 解答:归纳法的步骤如下:

  1. 初始情况$i = 0$时,$F_0 = (\phi^0 - \hat{\phi^0})/\sqrt{5} = 0$,$i = 1$时,$F_1 = (\phi - \hat{\phi})/\sqrt{5} = 1$,符合
  2. 证明当$n=k-2$和$n=k-1$成立,$n = k$时也成立,代入公式,符合

即可得证。

3.2-8 解答:待完成

思考题

待完成。