《算法导论》第三章-思考题（参考答案）

函数的增长

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)$

e. $f(n) = \sqrt{n}$ 。设 $n$ 经过 $i$ 次开根号，余下的数小于等于 2，即 $f^*_c(\sqrt{n}) = i$ ，则

$n^{{{\frac{1}{2}}^{\frac{1}{2}}}^{...}} \leq 2$

$n^{{\frac{1}{2}}^i} \leq 2$

$n \leq 2^{2^i}$

$\lg n \leq 2^i$

$\lg \lg n \leq i$

即： $0 \leq \lg \lg n \leq f^*_c(\sqrt{n})$ ，故 $f^*_c(n) =\Theta(\lg \lg n)$ 。

h. $f(n) = \frac{n}{\lg n}$ ，当 $n$ 足够大时，

$\frac{n}{\sqrt{n}} < \frac{n}{\lg n} < \frac{n}{2}$

由上表易得， $f^*_c(\frac{n}{\lg n}) = \omega(\lg \lg n), f^*_c(\frac{n}{\lg n}) = o(\lg n)$ 。

最后编辑于：2019.10.10 19:56:00

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 204,921评论 6赞 478
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 87,635评论 2赞 381
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 151,393评论 0赞 338
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 54,836评论 1赞 277
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 63,833评论 5赞 368
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 48,685评论 1赞 281
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 38,043评论 3赞 399
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 36,694评论 0赞 258
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 42,671评论 1赞 300
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 35,670评论 2赞 321
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 37,779评论 1赞 332
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 33,424评论 4赞 321
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 39,027评论 3赞 307
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 29,984评论 0赞 19
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 31,214评论 1赞 260
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 45,108评论 2赞 351
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 42,517评论 2赞 343

《算法导论》第三章-思考题（参考答案）

函数的增长

3.1

3-2

3.3

3-4

3-5

3-6

推荐阅读更多精彩内容