函数的增长

3.1

（多项式的渐进行为）假设 $p(n) = \sum \limits_{i=1}^{d} a_i n^i$ 是一个关于 $n$ 的 $d$ 次多项式，其中 $a_d > 0$ ， $k$ 是一个常量。使用渐进符号的定义来证明下面的性质。

a. 若 $k \geq d$ ，则 $p(n) = O(n^k)$ 。

b. 若 $k \leq d$ ，则 $p(n) = \Omega(n^k)$ 。

c. 若 $k = d$ ，则 $p(n) = \Theta(n^k)$ 。

d. 若 $k > d$ ，则 $p(n) = o(n^k)$ 。

e. 若 $k < d$ ，则 $p(n) = \omega(n^k)$ 。

已知： $p(n) = \sum \limits_{i=1}^{d} a_i n^i$ ，易得 $p(n) = \Theta(n^d)$ 。

故 $p(n) = O(n^d), p(n) = \Omega(n^d)$ 。

情况 1：

$\because k \geq d, \therefore n^k \geq n^d$ ，即： $n^d = O(n^k)$ 。

故 $p(n) = O(n^k)$ 。

情况 2：

$\because k \leq d, \therefore n^k \leq n^d$ ，即： $n^d = \Omega(n^k)$ 。

故 $p(n) = \Omega(n^k)$ 。

情况 3：

$\because k = d, \therefore n^k = n^d$ ，即： $n^d = \Theta(n^k)$ 。

故 $p(n) = \Theta(n^k)$ 。

情况 4：

$\because k > d, \therefore n^k > n^d$ ，即： $n^d = o(n^k)$ 。

故 $p(n) = o(n^k)$ 。

情况 5：

$\because k < d, \therefore n^k < n^d$ ，即： $n^d = \omega(n^k)$ 。

故 $p(n) = \omega(n^k)$ 。

3-2

（相对渐进增长）为下表中的每对表达式 $(A, B)$ 指出 $A$ 是否是 $B$ 的 $O、o、\Omega、\omega$ 或 $\Theta$ 。假设 $k \geq 1、 \epsilon > 0$ 且 $c > 1$ 均为常量。回答应以表格的形式，将“是”或“否”写在每个空格中。

	$A$	$B$	$O$	$o$	$\Omega$	$\omega$	$\Theta$
a.	$\lg^k n$	$n^{\epsilon}$	否	否	是	是	否
b.	$n^k$	$c^n$	否	否	是	是	否
c.	$\sqrt{n}$	$n^{\sin n}$	否	否	否	否	否
d.	$2^n$	$n^{\frac{n}{2}}$	是	是	否	否	否
e.	$n^{\lg c}$	$c^{\lg n}$	是	否	是	否	是
f.	$\lg(n!)$	$\lg(n^n)$	是	否	是	否	是

$\lim \limits_{n \to +\infty} \frac{n^b}{a^n} = 0$

令 $\lg n$ 代替 $n$ ，并令 $2^a$ 代替 a，可得：

$\lim \limits_{n \to +\infty} \frac{\lg^b n}{2^{a \lg n}} = \lim \limits_{n \to +\infty} \frac{\lg^b n}{n^a} = 0$

即： $n^\epsilon = \omega(\lg^b n)$ 。

又：若 $\forall n < 0, n^b <0$ 。故： $n^\epsilon = \Omega(\lg^b n)$ 。

$\lim \limits_{n \to +\infty} \frac{n^k}{c^n} = 0$

故， $c^n = \omega(n^k)$ 。

令 $n=2, k = 3, c = 2, n^k = 8 > c^n = 4$ 。故 $c^n = \Omega(n^k)$ 。

$\sqrt{n} = n^{\frac{1}{2}}$ 。又 $\sin n$ 的值为在区间 $[0, 1]$ 中波动，故 $\sqrt{n}$ 与 $n^{\sin n}$ 无任何关系

$\because 2^n$ 严格递增，故对于任意正常量 $c$ ，总存在 $n_0 > 0$ ，使得 $\forall n \geq n_0, 0 \leq 2^{\frac{n}{2}} < 2^n$ ，即：

$2^{\frac{n}{2}} = o(2^n)$

也易证：故对于任意正常量 $c$ ，总存在 $n_0 \geq 0$ ，使得 $\forall n \geq n_0, 0\leq 2^{\frac{n}{2}} \leq 2^n$ ，即：

$2^{\frac{n}{2}} = O(2^n)$

$n^{\lg c} = c^{\lg a}$ 。故 $c^{\lg n} = \Theta(n^{\lg c})$ 。

$\lg(n^n) = n \lg n$

$\lg(n!) = \sum \limits_{i = 1}^{n} \lg i \leq \sum \limits_{i = 1}^{n} \lg n = n \lg n$

故， $\lg(n^n) = \Omega(\lg (n!))$

又， $\lg n$ 是严格递增的函数。故， $\forall i \geq \frac{n}{2}, f(i) \geq f(\frac{n}{2})$

$\sum \limits_{i = 1}^{n} \lg i \geq \frac{n}{2} \lg \frac{n}{2} = \frac{n}{2} \lg(n - 1)$

故， $\lg(n!) = \Omega(\lg(n^n))$ ，也即 $\lg(n^n) = O(\lg (n!))$

也即 $\lg(n^n) = \Theta(\lg(n!))$

3.3

（根据渐进增长率排序）

a. 根据增长的阶来排序下面的函数，即求出满足 $g_1 = \Omega(g_2), g_2 = \Omega(g_3), ..., g_{29} = \Omega(g_{30})$ 的函数的一种排列 $g_1, g_2, ..., g_{30}$ 。把你的表划分成等价类，使得函数 $f(n)$ 和 $g(n)$ 在相同类中当且仅当 $f(n) = \Theta(g(n))$ 。

$\lg(\lg^* n)$	$2^{\lg^* n}$	$(\sqrt 2)^{\lg n}$	$n^2$	$n!$	$(\lg n)!$
$(\frac{3}{2})^n$	$n^3$	$\lg^2 n$	$\lg(n!)$	$2^{2^n}$	$n^{\frac{1}{\lg n}}$
$\ln \ln n$	$\lg^* n$	$n * 2^n$	$n^{\lg \lg n}$	$\ln n$	$1$
$2^{\lg n}$	$(\lg n)^{\lg n}$	$e^n$	$4^{\lg n}$	$(n + 1)!$	$\sqrt{\lg n}$
$\lg^* (\lg n)$	$2^{\sqrt{2 \lg n}}$	$n$	$2^n$	$n \lg n$	$2^{2^{n + 1}}$

五.六 $2^{2^{n + 1}}$
二.五 $2^{2^n}$
四.五 $(n + 1)!$
一.五 $n!$
四.三 $e^n$
三.三 $n * 2^n$
五.四 $2^n$
二.一 $(\frac{3}{2})^n$
三.四 $n^{\lg \lg n} = (\lg n)^{\lg n}$ 四.二
一.六 $(\lg n)!$
二.二 $n^3$
一.四 $n^2 = n^{\lg 4} = 4^{\lg n}$ 四.四
五.五 $n \lg n = \lg n^n \geq \lg(n!)$ 二.四
五.三 $n = n^{\lg 2} = 2^{\lg n}$ 四.一
一.三 $(\sqrt 2)^{\lg n}$
五.二 $2^{\sqrt{2 \lg n}}$
二.三 $\lg^2 n$
三.五 $\ln n$
四.六 $\sqrt{\lg n}$
三.一 $\ln \ln n$
一.二 $2^{\lg^* n}$
三.二 $\lg^* n \approx \lg^* (\lg n)$ 六.一
一.一 $\lg(\lg^* n)$
二.六 $n^{\frac{1}{\lg n}} = 1$ 三.六

b.给出非负函数 $f(n)$ 的一个例子，使得对所有在（a）部分中的函数 $g_i(n)$ ， $f(n)$ 既不是 $O(g_i(n))$ 也不是 $\Omega(g_i(n))$ 。

$n^{\sin n + 1}$

3-4

（渐进记号的性质）假设 $f(n)$ 和 $g(n)$ 为渐进正函数。证明或反驳下面的每个猜测。

a. $f(n) = O(g(n))$ 蕴含 $g(n) = O(f(n))$ 。

错。例如： $n = O(n^2)$ 。

b. $f(n) + g(n) = \Theta(\min(f(n), g(n)))$ 。

错。例如： $n + n^2 = \Theta(n^2) \neq \Theta(n, n^2) = \Theta(n)$ 。

c. $f(n) = O(g(n))$ 蕴含 $\lg (f(n)) = O(\lg(g(n)))$ ，其中对所有足够大的 $n$ ，有 $\lg(g(n)) \geq 1$ 且 $f(n) \geq 1$ 。

正确。

对于足够大的 $n$ ，有 $f(n) \geq 1$ ；且 $f(n) = O(g(n))$ ，则存在正常量 $c, n_0$ ，使得 $\forall n \geq n_0$ ，有

$0 \leq f(n) \leq cg(n)$

$0 \leq \lg(f(n)) \leq \lg c \lg(g(n))$

又 $\because \lg(g(n)) \geq 1$ ，故当 $c' = \lg c + 1$ ，且 $n_0'$ 足够大，有：

$\lg(f(n)) \leq \lg c + \lg(g(n)) \leq (\lg c + 1) \lg(g(n)) \leq c' \lg(g(n))$

故原问题成立。

d. $f(n) = O(g(n))$ 蕴含 $2^{f(n)} = O(2^{g(n)})$ 。

错。例如： $2n = O(n), 2^{2n} = 4^n \neq O(2^n)$ 。

e. $f(n) = O((f(n))^2)$ 。

当 $f(n) \geq 1$ 时， $f(n)^2 \geq f(n), f(n) = O(f(n)^2)$ ；其他条件下，不成立。

f. $f(n) = O(g(n))$ 蕴含 $g(n) = \Omega(f(n))$ 。

正确。 $f(n) = O(g(n))$ ，即存在正常量 $c、 n_0$ ，使得 $\forall n\geq n_0$ ，有

$0 \leq f(n) \leq cg(n)$ ，即 $0 \leq \frac{1}{c} f(n) \leq g(n)$

令 $c' = \frac{1}{c}, n_0' = n_0$ ，得 $g(n) = \Omega(f(n))$ 。

g. $f(n) = \Theta(f(\frac{n}{2}))$ 。

错。例如： $n! \neq \Theta((\frac{n}{2})!)$ 。

h. $f(n) + o(f(n)) = \Theta(f(n))$ 。

正确。

易得， $f(n) = \Theta(f(n))$ ，即存在正常量 $c_1, c_2, n_1$ ，使得 $\forall n\geq n_1$ ，都有 $0 \leq c_1 f(n) \leq f(n) \leq c_2 f(n)$ 。

令 $g(n) = o(f(n))$ ，即存在正常量 $c, n_2$ ，使得 $\forall n\geq n_2$ ，都有 $0 \leq g(n) < c f(n)$ 。

令 $n_0 = \max(n_1, n_2)$ ，则 $\forall n\geq n_0$ ，有 $0 \leq c_1 f(n) \leq f(n) + g(n) \leq (c_2 + c) f(n)$ 。

即 $f(n) + o(f(n)) = \Theta(f(n))$ 。

3-5

（ $O$ 与 $\Omega$ 的一些变形）某些作者用一种与我们稍微不同的方式来定义 $\Omega$ ；假设我们使用 $\Omega^\infty$ （读作“ $\Omega$ 无穷”）来标识这种可选的定义。若存在正常量 $c$ ，使得对无穷多个整数 $n$ ，有 $f(n) \geq cg(n) \geq 0$ ，则称 $f(n) = \Omega^\infty(g(n))$ 。

a. 证明：对渐进非负的任意两个函数 $f(n)$ 和 $g(n)$ ，或者 $f(n) = O(g(n))$ 或者 $f(n) = \Omega^\infty(g(n))$ 或者二者均成立，然而，如果使用 $\Omega$ 来代替 $\Omega^\infty$ ，那么该命题并不为真。

$\Omega^\infty$ 主要缺少了 $n \geq n_0$ 这个条件；则若 $f(n) \neq O(g(n))$ ，必然有无穷多个正整数 $n$ ，使得 $f(n) \geq cg(n) \geq 0$ 成立；

若 $f(n) = \Theta(g(n))$ ，则上述两者均成立；

反例： $n = \Omega^\infty(n^{\sin n})$ ，但 $n \neq \Omega(n^{\sin n})$ 。

b. 描述用 $\Omega^\infty$ 代替 $\Omega$ 来刻画程序运行时间的潜在优点与缺点。

优点： $\Omega^\infty$ 对下届的要求更宽松，可以兼容更多的情况；

缺点： $\Omega\infty$ 并非严格的渐进下界。因此实际意义并不大。

某些作者也用一种稍微不同的方式来定义 $O$ ；假设使用 $O'$ 来标识这种可选的定义。我们称 $f(n) = O'(g(n))$ 当且仅当 $|f(n)| = O(g(n))$ 。

c. 如果使用 $O'$ 代替 $O$ 但仍然使用 $\Omega$ ，定理 3.1 中的“当且仅当”的每个方向将出现什么情况？

没有变化。 $f(n) = O(n)$ 成立意味着 $f(n)$ 渐进非负，故 $|f(n)| = f(n)$ 。

有些作者定义 $\breve{O}$ （读作“软 $O$ ”）来意指忽略对数因子的 $O$ ：

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

d. 用一种类似的方式定义 $\breve{\Omega}$ 和 $\breve{\Theta}$ 。证明与定理 3.1 相对应的类似结论。

$\breve{\Omega}(g(n)) = \{f(n)$ ：存在正常量 $c, k$ 和 $n_0$ ，使得对所有 $n \geq n_0$ ，有 $0 \leq cg(n) \lg^k(n) \leq f(n) \}$ 。

$\breve{O}(g(n)) = \{f(n)$ ：存在正常量 $c_1, c_2, k_1, k_2$ 和 $n_0$ ，使得对所有 $n \geq n_0$ ，有 $0 \leq c_1 g(n) \lg^{k_1}(n) \leq f(n) \leq c_2 g(n) \lg^{k_2}(n) \}$ 。

3-6

（多重函数） 我们可以把用于函数 $\lg^*$ 中的多重操作符 * 应用于实数集上的任意单调递增函数 $f(n)$ 。对给定的常量 $c \in R$ ，我们定义多重函数 $f^*_c$ 为

$f^*_c(n) = \min\{i \geq 0:f^{(i)}(n) \leq c\}$

该函数不必再所有情况下都是良定义的。换句话说，值 $f^*_c(n)$ 是为缩小其参数到 $c$ 或更小所需函数 $f$ 重复应用的数目。

对如下每个函数 $f(n)$ 和常量 $c$ ，给出 $f^*_c(n)$ 的一个尽量紧确的界。

	$f(n)$	$c$	$f^*_c(n)$
a.	$n - 1$	0	$\Theta(n)$
b.	$\lg n$	1	$\Theta (\lg^* n)$
c.	$\frac{n}{2}$	1	$\Theta(\lg n)$
d.	$\frac{n}{2}$	2	$\Theta(\lg n)$
e.	$\sqrt{n}$	2	$\Theta(\lg \lg n)$
f.	$\sqrt{n}$	1	无法收敛
g.	$n^{\frac{1}{3}}$	2	$\Theta(\log_3 \lg n)$
h.	$\frac{n}{\lg n}$	2	$\omega(\lg \lg n), o(\lg n)$