《算法导论》第三章 3.1（参考答案）

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 > n_f$ 时， $f(n) \geq 0$ ；
当 $n > n_g$ 时， $g(n) \geq 0$ 。

所以，我们取 $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)$

所以，得证！。

3.1-2

证明：对任意实常数 $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 + a \leq n + |a| \leq 2n, |a| \leq n$
$n + a \geq n - |a| \geq \frac{1}{2}n, |a| \leq \frac{1}{2}n$

故，若 $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)$ 。

3.1-3

解释为什么“算法 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$ 这一无需证明的结论而已。

3.1-4

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

证明定理 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))$ 。

3.1-6

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

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

3.1-7

证明： $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)))$ 。则有：

$\lim \limits_{n \rightarrow + \infty} \frac{f(n)}{g(n)} = 0$
$\lim \limits_{n \rightarrow + \infty} \frac{f(n)}{g(n)} = +\infty$

很明显，不成立。

3.1-8

可以扩展我们的记号到有两个参数 $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) \}$ 。

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