算法导论第 3 章：函数的增长
主要内容
本章讲解如何简化算法的渐近分析，介绍了几类渐近记号。最后简单介绍了常用函数的性质。本章的内容在这里描述得非常简略，但为了保持整个系列的完整性，还是贴出来了。
渐近记号
本章介绍了如下渐近记号，它们的严格定义分别如下：
- 若\(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)\)
- 若\(f(n) = O(g(n))\)，则存在正常量\(c\)和\(n_0\)，使得对所有\(n \ge n_0\)，有\(0 \le f(n) \le c g(n)\)
- 若\(f(n) = \Omega(g(n))\)，则存在正常量\(c\)和\(n_0\)，使得对所有\(n \ge n_0\)，有\(0 \le c g(n) \le f(n)\)
- 若\(f(n) = o(g(n))\)，则对任意\(c>0\)，存在常量\(n_0>0\)，使得对所有\(n \ge n_0\)，有\(0 \le f(n) < c g(n)\)
- 若\(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\)的符号分情况讨论：
- 当\(a > 0\)时，令\(n \ge n_0 = a\)，则有\(1 \le 1+a/n \le 2\)，即\(c_1 = 1, c_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-6 解答：根据黄金分割率的定义有：\(\phi / 1 = \phi / (1 - \phi)\)，即满足方程\(x^2 = x + 1\)，得证。
3.2-7 解答：归纳法的步骤如下：
- 初始情况\(i = 0\)时，\(F_0 = (\phi^0 - \hat{\phi}^0)/\sqrt{5} = 0\)，\(i = 1\)时，\(F_1 = (\phi - \hat{\phi})/\sqrt{5} = 1\)，符合
- 证明当\(n=k-2\)和\(n=k-1\)成立，\(n = k\)时也成立，代入公式，符合
即可得证。