本文共 14640 字，大约阅读时间需要 48 分钟。

Part I. Foundations
Chapter 3. Growth of Functions

3.1 渐近记号（Asymptotic notation）

$\Theta$ 记号

对于一个给定的函数 $g(n)$，我们用 $\Theta (g(n))$ 表示函数集合：
Θ ( g ( n ) ) = { f ( n ) \Theta(g(n))=\{f(n) Θ(g(n))={ f(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)\}$.

因为 $\Theta (g(n))$ 是一个集合，可以写成 $f(n)\in \Theta (g(n))$，表示 $f(n)$ 是 $\Theta (g(n))$ 的元素。不过，通常写成 $f(n)=\Theta (g(n))$ 表示相同的意思。
对于所有的 $n>n_0$，函数 $f(n)$ 在一个常量因子范围内与 $g(n)$ 相等。我们说 $g(n)$ 是 $f(n)$ 的一个渐近紧确界（asymptotically tight bound）。
$\Theta (g(n))$ 的定义要求每个成员 $f(n)\in \Theta (g(n))$ 是渐近非负（asymptotically nonnegative），也就是说，当 $n$ 足够大时，$f(n)$ 的值非负。因此，函数 $g(n)$ 必须是渐近非负的，否则集合 $\Theta (g(n))$ 为空。
渐近正（asymptotically positive）函数：当 $n$ 足够大时，其值总为正值。
我们假定在 $\Theta$ 记号内使用的每个函数都是渐近非负的。该假设也适用于本章中定义的其他渐近记号。

$O$ 记号

对于一个给定的函数 $g(n)$，我们用 $O(g(n))$ 表示函数集合：
O ( g ( n ) ) = { f ( n ) O(g(n))=\{f(n) O(g(n))={ f(n)：存在正常数 $c$ 和 $n_0$，使对所有 $n\ge n_0$，有 $0\le f(n)\le cg(n)\}$。

$\Theta$ 记号渐近地给出一个函数的上界和下界。当只有渐近上限（asymptotic upper bound）时，使用 $O$ 记号。
$O(g(n))$ 发音：“big-oh of g of n”（$g(n)$ 的大 $O$），或者有时读作 “oh of g of n”。
$f(n)=O(g(n))$ 表示函数 $f(n)$ 是集合 $O(g(n))$ 的一个元素。
按集合论中的写法，有 $\Theta (g(n))\subseteq O(g(n))$。$\Theta$ 记号强于 $O$ 记号。

$\Omega$ 记号

对于一个给定的函数 $g(n)$，我们用 $\Omega (g(n))$ 表示函数集合：
Ω ( g ( n ) ) = { f ( n ) \Omega(g(n))=\{f(n) Ω(g(n))={ f(n)：存在正常数 $c$ 和 $n_0$，使对所有 $n\ge n_0$，有 $0\le cg(n)\le f(n)\}$。

$\Omega$ 记号给出函数的渐近下界（asymptotic lower bound）。
$\Omega (g(n))$ 的发音：“big-omega of g of n”，或者有时读作 “omega of g of n”。

定理 3.1

对任意两个函数 $f(n)$ 和 $g(n)$，当且仅当 $f(n)=O(g(n))$，$f(n)=\Omega (g(n))$ 时，有 $f(n)=\Theta (g(n))$。

等式和不等式中渐近记号

等式：$2n^2+3n+1=2n^2+\Theta (n)=\Theta (n^2)$
解释：第一个等式说明存在函数 $f(n)\in \Theta (n)$，使对所有的 $n$ 有 $2n^2+3n+1=2n^2+f(n)$。第二个等式说明对任意函数 $g(n)\in \Theta (n)$，存在函数 $h(n)\in \Theta (n^2)$，使对所有的 $n$ 有 $2n^2+g(n)=h(n)$。
规则：无论等号左侧的匿名函数如何选择，总有方法选择等号右侧的匿名函数以使方程有效。

$o$ 记号

我们使用 $o$ 记号表示非渐近紧确的上界。定义 $o(g(n))$（“little-oh of g of n”）为集合：
o ( g ( n ) ) = { f ( n ) o(g(n))=\{f(n) o(g(n))={ f(n)：对任意正常数 $c$，存在常数 $n_0>0$，使对所有 $n\ge n_0$，有 $0\le f(n)\le cg(n)\}$。
例如，$2n=o(n^2)$，但是 $2n^2\ne o(n^2)$。

直观上，在 $o$ 表示中，当 $n$ 趋于无穷时，函数 $f(n)$ 相对于 $g(n)$ 变得无关紧要，即
${\lim }_{n\to \infty }\frac{f(n)}{g(n)}=0$。       (3.1)
某些作者将这个极限作为 $o$ 记号的定义。

$\omega$ 记号

我们使用 $\omega$ 记号表示非渐近紧确的下界。定义 $\omega (g(n))$（“little-omega of g of n”）为集合：
ω ( g ( n ) ) = { f ( n ) \omega(g(n))=\{f(n) ω(g(n))={ f(n)：对任意正常数 $c$，存在常数 $n_0>0$，使对所有 $n\ge n_0$，有 $0\le cg(n)\le f(n)\}$。
例如，$n^2/2=\omega (n)$，但是 $n^2/2\ne \omega (n^2)$。

$\omega$ 记号的另一种定义：$f(n)\in \omega (g(n))$，当且仅当 $g(n)\in o(f(n))$。
关系 $f(n)=\omega (g(n))$ 意味着
${\lim }_{n\to \infty }\frac{f(n)}{g(n)}=\infty$。

函数的比较

下面假设 $f(n)$ 和 $g(n)$ 是渐近正值函数。
传递性（Transitivity）：
$f(n)=\Theta (g(n))$ 和 $g(n)=\Theta (h(n))$   蕴含 $f(n)=\Theta (h(n))$，
$f(n)=O(g(n))$ 和 $g(n)=O(h(n))$   蕴含 $f(n)=O(h(n))$，
$f(n)=\Omega (g(n))$ 和 $g(n)=\Omega (h(n))$   蕴含 $f(n)=\Omega (h(n))$，
$f(n)=o(g(n))$ 和 $g(n)=o(h(n))$   蕴含 $f(n)=o(h(n))$，
$f(n)=\omega (g(n))$ 和 $g(n)=\omega (h(n))$   蕴含 $f(n)=\omega (h(n))$。
自反性（Reflexivity）：
$f(n)=\Theta (f(n))$，
$f(n)=O(f(n))$，
$f(n)=\Omega (f(n))$。
对称性（Symmetry）：
$f(n)=\Theta (g(n))$ 当且仅当 $g(n)=\Theta (f(n))$。
转置对称性（Transpose symmetry）：
$f(n)=O(g(n))$ 当且仅当 $g(n)=\Omega (f(n))$，
$f(n)=o(g(n))$ 当且仅当 $g(n)=\omega (f(n))$。

如果 $f(n)=o(g(n))$，那么 $f(n)$ 比 $g(n)$ 渐近较小（asymptotically smaller）；
如果 $f(n)=\omega (g(n))$，那么 $f(n)$ 比 $g(n)$ 渐近较大（asymptotically larger）。

三分性（Trichotomy）： 对任意两个实数 $a$ 和 $b$，下列三种情况恰有一种成立：$a<b$，$a=b$ 或 $a>b$。
渐近记号不满足实数的三分性。

练习

3.1-1 设 $f(n)$ 和 $g(n)$ 是渐近非负函数，利用 $\Theta$ 记号的基本定义来证明 $\max (f(n),g(n))=\Theta (f(n)+g(n))$。
证： 根据 $\Theta$ 记号的定义知，需要证明：存在正常数 $c_1$、$c_2$ 和 $n_0$，使对所有 $n\ge n_0$，
有 $0\le c_1(f(n)+g(n))\le \max (f(n),g(n))\le c_2(f(n)+g(n))$。

因为 $f(n)$ 和 $g(n)$ 渐近非负，所以存在正常数 $m_0$，使对所有 $n\ge m_0$，有 $f(n)\ge 0$，$g(n)\ge 0$。
令 $h(n)=\max (f(n),g(n))$，
则有 $f(n)\le h(n)$，$g(n)\le h(n)$，$h(n)<f(n)+g(n)$。
所以 $f(n)+g(n)\le 2h(n)$，得出 $(f(n)+g(n))/2\le h(n)$。
综上，存在正常数 $c_1=1/2$，$c_2=1$ 和 $n_0=m_0$，满足条件，得证。

3.1-2 证明：对任意实数常量 $a$ 和 $b$，其中 $b>0$，有
$(n+a{)}^b=\Theta (n^b)$。       (3.2)
证： 根据 $\Theta$ 记号的定义知，需要证明：存在正常数 $c_1$、$c_2$ 和 $n_0$，使对所有 $n\ge n_0$，
有 $0\le c_1{n}^b\le (n+a{)}^b\le c_2{n}^b$。
当 $n>0$ 时，$n^b>0$，则有 $0\le c_1\le (1+a/n{)}^b\le c_2$。

当 $a\ge 0$ 时，
令 $n>0$，则有 $1+a/n>1$，又 $b>0$，所以 $(1+a/n{)}^b>1$。
令 $n\ge |a|$，则有 $1+a/n\le 2$，所以 $(1+a/n{)}^b\le 2^b$。
当 $a<0$ 时，
令 $n\ge 2|a|$，则有 $1-|a|/n\ge 1/2$，又 $b>0$，所以 $(1+a/n{)}^b\ge (1/2{)}^b$。
令 $n\ge |a|$，则有 $1-|a|/n\le 1$，所以 $(1+a/n{)}^b\le 1$。
因为 $b>0$，所以 $0<(1/2{)}^b<1<2^b$。

综上，存在正常数 $c_1=(1/2{)}^b$，$c_2=2^b$，$n_0=2|a|$，满足条件，得证。

3.1-3 解释：为什么“算法 $A$ 的运行时间至少是 $O(n^2)$”这句话是无意义的。
解： 设运行时间为 $T(n)$。$T(n)\ge O(n^2)$ 表示：对于集合 $O(n^2)$ 中的某些函数 $f(n)$，$T(n)\ge f(n)$。该语句适用于任何运行时间 $T(n)$，因为对于所有 $n$，在 $O(n^2)$ 中均存在函数 $g(n)=0$，而运行时间始终为非负数。 因此，该声明没有告诉我们有关运行时间的任何信息。

3.1-4 $2^{n+1}=O(2^n)$ 成立吗？$2^{2n}=O(2^n)$ 成立吗？
解： $2^{n+1}=O(2^n)$ 成立，$2^{2n}=O(2^n)$ 不成立。
① 要证明 $2^{n+1}=O(2^n)$ 成立，需证存在正常数 $c$ 和 $n_0$，使对所有 $n\ge n_0$，有 $0\le 2^{n+1}\le c\cdot 2^n$。
当 $n>0$ 时，$2^n>1$，由上式得，$0\le 2\le c$。
综上，存在正常数 $c=2$，$n_0=1$，使条件成立，得证。
② 要证明 $2^{2n}=O(2^n)$ 不成立，可以使用反证法。假设 $2^{2n}=O(2^n)$ 成立，那么存在正常数 $c$ 和 $n_0$，使对所有 $n\ge n_0$，有 $0\le 2^{2n}\le c\cdot 2^n$，即 $0\le 2^n\le c$。
当 $n>0$ 时，$2^n$ 的值域为 $(1,\infty )$。
所以，不存在常数 $c$，使 $c\ge 2^n$ 恒成立。与假设矛盾，得证。

3.1-5 证明定理 3.1。
证： 要证明定理 3.1，需证：对任意两个函数 $f(n)$ 和 $g(n)$，
① $f(n)=O(g(n)),f(n)=\Omega (g(n))⟹f(n)=\Theta (g(n))$，
② $f(n)=\Theta (g(n))⟹f(n)=O(g(n)),f(n)=\Omega (g(n))$。
先证明 ① 成立，要证明 $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))$，得：存在正常数 $a$ 和 $m_1$，使对所有 $n\ge m_1$，有 $0\le f(n)\le ag(n)$。
由 $f(n)=\Omega (g(n))$，得：存在正常数 $b$ 和 $m_2$，使对所有 $n\ge m_2$，有 $0\le bg(n)\le f(n)$。
所以，存在正常数 $c_1=b$，$c_2=a$，$n_0=\max (m_1,m_2)$，满足条件，得证。
再证明 ② 成立。由 $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)$。
故，存在正常数 $c_2$ 和 $n_0$，使对所有 $n\ge n_0$，有 $0\le f(n)\le c_{2}g(n)$，所以 $f(n)=O(g(n))$ 成立；存在正常数 $c_1$ 和 $n_0$，使对所有 $n\ge n_0$，有 $0\le c_{1}g(n)\le f(n)$，所以$f(n)=\Omega (g(n))$ 成立。得证。
综上，定理 3.1 成立。

3.1-6 证明：一个算法的运行时间是 $\Theta (g(n))$，当且仅当最坏情况运行时间是 $O(g(n))$，最佳情况运行时间是 $\Omega (g(n))$。
证： 设算法的运行时间是 $T(n)$，由定理 3.1 得，
$T(n)=O(g(n)),T(n)=\Omega (g(n))⟺T(n)=\Theta (g(n))$。

3.1-7 证明 $o(g(n))\cap \omega (g(n))$ 是空集。
证： 反证法。假设存在函数 $h(n)\in o(g(n))\cap \omega (g(n))$，即 $h(n)=o(g(n))$，$h(n)=\omega (g(n))$。
由 $h(n)=o(g(n))$，得：对任意正常数 $c$，存在常数 $n_1>0$，使对所有 $n\ge n_1$，有 $0\le h(n)\le cg(n)$。
由 $h(n)=\omega (g(n))$，得：对任意正常数 $c$，存在常数 $n_2>0$，使对所有 $n\ge n_2$，有 $0\le cg(n)\le h(n)$。
故，对任意正常数 $c$，存在常数 $n_0=\max (n1,n2)$，使对所有 $n\ge n_0$，有 $h(n)=cg(n)$。
所以，$h(n)=0$，$g(n)=0$。
根据转置对称性，得 $g(n)=o(h(n))$，即，对任意正常数 $c$，存在常数 $m_1>0$，使对所有 $n\ge m_1$，有 $0\le g(n)\le ch(n)$。
所以，对任意正常数 $c$，存在常数 $n_0=\max (n1,m1)$，使对所有 $n\ge n_0$，有 $0\le h(n)\le cg(n)\le c^{2}h(n)$，得 $0\le h(n)\le c^{2}h(n)$，即 $c^2>1$，与 $c$ 为任意正常数相矛盾。
所以不存在函数 $h(n)\in o(g(n))\cap \omega (g(n))$，所以 $o(g(n))\cap \omega (g(n))$ 是空集。

3.1-8 可以将我们的记号扩展为有两个参数 $n$ 和 $m$ 的情况，其中，$n$ 和 $m$ 可以以不同的速率，互相独立地趋于无穷。对于给定的函数 $g(n,m)$，我们用 $O(g(n,m))$ 表示函数集：
O ( g ( n , m ) ) = { f ( n , m ) : O(g(n,m))=\{f(n,m): O(g(n,m))={ f(n,m): 存在正整数 $c$，$n_0$ 和 $m_0$，使对所有 $n⩾n_0$ 及 $m⩾m_0$，有 $0⩽f(n,m)⩽cg(n,m)\}$。
给出对应的 $\Omega (g(n,m))$ 和 $\Theta (g(n,m))$ 的定义。
解： Ω ( g ( n , m ) ) = { f ( n , m ) : \Omega(g(n,m))=\{f(n,m): Ω(g(n,m))={ f(n,m): 存在正整数 $c$，$n_0$ 和 $m_0$，使对所有 $n⩾n_0$ 及 $m⩾m_0$，有 $0⩽cg(n,m)⩽f(n,m)\}$。
Θ ( g ( n , m ) ) = { f ( n , m ) : \Theta(g(n,m))=\{f(n,m): Θ(g(n,m))={ f(n,m): 存在正整数 $c_1$，$c_2$，$n_0$ 和 $m_0$，使对所有 $n⩾n_0$ 及 $m⩾m_0$，有 $0⩽c_{1}g(n,m)⩽f(n,m)⩽c_{2}g(n,m)\}$。

学习笔记目录：