算法导论第 3 章：函数的增长

主要内容

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

渐近记号

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

1. 若，则存在正常量、和，使得对所有，有
2. 若，则存在正常量和，使得对所有，有
3. 若，则存在正常量和，使得对所有，有
4. 若，则对任意，存在常量，使得对所有，有
5. 若，则对任意，存在常量，使得对所有，有

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

• 类似于
• 类似于
• 类似于
• 类似于
• 类似于

标准记号与常用函数

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

习题解答

练习题

3.1-1 解答：即需证明存在正常数，和，使得当时有：

由于和均是渐近非负函数，所以存在，使得当时，有和。令

则

所以有

又有

所以存在，和满足条件，得证。

3.1-2 解答：即需证明存在正常数，和，使得当时有：

即

当时，幂函数在上单调递增。下面根据的符号分情况讨论：

1. 当时，令，则有，即，根据幂函数的单调性，上式成立；
2. 当时，，令，则有，即，根据幂函数的单调性，上式成立。

所以得证。

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

3.1-4 解答：成立，不成立。

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

根据数列极限的定义，对任意，存在自然数使得当时，有。

根据的定义，对任意正常量，存在，使得对所有，有，即，取，，得证。

3.1-6 解答：记号提供了一个渐近上界，记号提供了渐近下界，所以为。严格证明略。

3.1-7 解答：类似于和不可能同时成立。

3.1-8 解答：，则存在正常量, 和，使得对所有的或，有

，则存在正常量，，和，使得对所有的或，有

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

3.2-2 解答：由公式得：

得证。

3.2-3 解答：要证明的(3.19)式为，借助斯特林近似公式，证明如下：

要证明，证明即可，代入斯特林近似公式即得证。

要证明，证明即可。令，则：

当时，，当时，，所以，所以的极限为。

3.2-6 解答：根据黄金分割率的定义有：，即满足方程，得证。

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

1. 初始情况时，，时，，符合
2. 证明当和成立，时也成立，代入公式，符合

即可得证。