3.1 渐进符号

3.1-1

假设 $f(n)$ 与 $g(n)$ 都是渐进非负函数。使用 $\Theta$ 记号的基本定义来证明 $max(f(n), g(n)) = \Theta(f(n) + g(n))$ 。

因为 $f(n)$ 与 $g(n)$ 都为渐进非负的函数，所以根据定义，有：

存在 $n_f$ 、 $n_g$ ，使得：

所以，我们取 $n_0 = max\{n_f, n_g\}$ ；此时，当 $n > n_0$ 时，同时有 $f(n) \geq 0, g(n) \geq 0$ 。

下面我们取 $c_1 = \frac{1}{2}, c_2 = 1$ ，根据 $f(n), g(n)$ 的渐进非负保证，当 $n > n_0$ 时，有：

$\frac{f(n) + g(n)}{2} \leq max\{f(n), g(n)\} \leq f(n) + g(n)$

所以，得证！。

证明：对任意实常数 $a$ 和 $b$ ，其中 $b > 0$ ，有 $(n + a)^b = \Theta(n^b)$ 。

为了证明 $(n + a)^b = \Theta(n^b)$ ，我们需要找到常量 $c_1, c_2, n_0 > 0$ ，使得：

对于所有的 $n \geq n_0$ ，有 $0 \leq c_1n^b \leq (n + a)^b \leq c_2n^b$ 。

其中：

故，若 $n \geq 2|a|, 0 \leq \frac{1}{2}n \leq n + a \leq 2a$ 。

易得，若 $b > 0$ ，有下列公式：

$0 \leq (\frac{1}{2}n)^b \leq (n + a)^b \leq (2n)^b$ ，即：

$0 \leq (\frac{1}{2})^bn^b \leq (n + a)^b \leq 2^bn^b$ 。

故，取 $c_1 = (\frac{1}{2})^b, c_2 = 2^b, n_0 = 2|a|$ ，即可证明 $(n + a)^b = \Theta(n^b)$ 。

解释为什么“算法 A 的运行时间至少是 $O(n^2)$ ”这一表述是无意义的。

设运行时间为 $T(n)$ 。则 $T(n) \geq O(n^2)$ 代表：

对于任意的 $f(n) \in O(n^2), T(n) \geq f(n)$ 。

也即 $0 \leq f(n) \leq cn^2，T(n) \geq f(n)$ 。

这只能说明 $T(n) \geq 0$ 这一无需证明的结论而已。

$2^{n + 1} = O(2^n)$ 成立吗？ $2^{2n} = O(2^n)$ 成立吗？

$2^{n + 1} = 2 * 2^n$ ，故：

对于任意的 $n_0 > 0， c \geq 2$ ，易得 $0 \leq 2^{n + 1} \leq c2^n， n \geq n_0$ 。

即 $2^{n + 1} = O(2^n)$ 成立。
反证法：若 $2^{2n} = O(2^n)$ 成立，则对 $n_0 > 0$ ，有 $0 \leq 2^{2n} \leq c2^n， n \geq n_0$ ；

又因为此时 $2^n \geq 0$ ，故有 $0 \leq 2^n \leq c$ ；

即 $n \leq \lg c$ 。显然这与趋向无穷的 n 是相悖的，

故 $2^{2n} = O(2^n)$ 不成立。

证明定理 3.1。

充分性：已知 $f(n) = \Theta(g(n))$ ，即存在 $c_1, c_2, n_0 > 0$ ，使得：

$0 \leq c_1g(n) \leq f(n) \leq c_2g(n)$ 。

故 $f(n) = O(g(n))$ 且 $f(n) = \Omega(g(n))$ 。
必要性：已知 $f(n) = O(g(n))$ ，则存在 $c_2, n_2 > 0$ ，使得：

$0 \leq f(n) \leq c_2g(n), n \geq n_2$ ；

且已知 $f(n) = \Omega(g(n))$ ，则存在 $c_1, n_1 > 0$ ，使得：

$0 \leq c_1g(n) \leq f(n), n \geq n_1$ 。

故，取 $n_0 = max\{n_1, n_2\}$ ，有

$0 \leq c_1g(n) \leq f(n) \leq c_2g(n), n \geq n_0$ 。

于是可得： $f(n) = \Theta(g(n))$ 。

证明：一个算法的运行时间为 $\Theta(g(n))$ ，则当且仅当其最坏情况运行时间为 $O(g(n))$ ，且其最好情况运行时间为 $\Omega(g(n))$ 。

由定义易可证， $\Theta$ 记号渐进地给出一个函数的上界及下界，且可分别由 $O$ 和 $\Omega$ 符号来表示其上下界。相对的，该算法的最坏和最好情况的运行时间也代表了该算法运行时间的上下界。故得证。

证明： $o(g(n)) \bigcap \omega(g(n))$ 为空集。

设 $f(n) \in (o(g(n)) \bigcup \omega(g(n)))$ ，也就代表着 $f(n) = o(g(n) = \omega(g(n)))$ 。则有：

很明显，不成立。

可以扩展我们的记号到有两个参数 $n$ 和 $m$ 的情形，其中的 $n$ 和 $m$ 可以按不同速率独立地趋于无穷。对于给定的函数 $g(n, m)$ ，用 $O(g(n, m))$ 来表示以下函数集：

$O(g(n, m)) = \{f(n, m)$ ：存在正常量 $c、n_0$ 和 $m_0$ ，使得对所有 $n \geq n_0$ 或 $m \geq m_0$ ，有 $0 \leq f(n, m) \leq cg(n, m) \}$ 。

对 $\Omega(g(n, m))$ 和 $\Theta(g(n, m))$ 给出相应的定义。

$\Omega (g(n, m)) = \{ f(n, m)$ ：存在正常量 $c、n_0$ 和 $m_0$ ，使得对所有 $n \geq n_0$ 或 $m \geq m_0$ ，有 $0 \leq cg(n, m) \leq f(n, m) \}$ 。
$\Theta (g(n, m)) = \{f(n, m)$ ：存在正常量 $c_1、c_2、n_0$ 和 $m_0$ ，使得对所有 $n \geq n_0$ 或 $m \geq m_0$ ，有 $0 \leq c_1 g(n, m) \leq f(n, m) \leq c_2 g(n, m) \}$ 。