0%

『算法导论』第 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 解答:待完成

思考题

待完成。