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

3.2 标准记号与常用函数

3.2-1

证明：若 $f(n)$ 和 $g(n)$ 是单调递增的函数，则函数 $f(n) + g(n)$ 和 $f(g(n))$ 也是单调递增的；此外，若 $f(n)$ 和 $g(n)$ 是非负的，则 $f(n) * g(n)$ 是单调递增的。

若 $f(n)、g(n)$ 单调递增，即对任意的 $n_1 \leq n_2$ 都有 $f(n_1) \leq f(n_2)，g(n_1) \leq g(n_2)$ 。故有：

$(f(n_1) + g(n_1)) - (f(n_2) + g(n_2)) = (f(n_1) - f(n_2)) + (g(n_1) - g(n_2)) \leq 0$ ；

$f(g(n_1)) - f(g(n_2)) \leq 0$ ；

即函数 $f(n) + g(n)$ 和 $f(g(n))$ 也是单调递增的。

若 $f(n)$ 和 $g(n)$ 是非负的，则 $f(n_1) * g(n_1) - f(n_2) * g(n_2) \leq 0$ ；

故 $f(n) * g(n)$ 是单调递增的。

3.2-2

证明等式（3.16）： $a^{\log_b c} = c^{\log_b a}$ 。

乘法交换律，得 $\log_b a * \log_b c = \log_b c * \log_b a$

又有 $z \log_x y = \log_x y^z$ ，得 $\log_b a^{\log_b c} = \log_b c^{\log_b a}$

又对数函数为严格递增函数，故 $a^{\log_b c} = c^{\log_b a}$

或：

$a^{\log_b c} = a^{\frac{\log_a c}{\log_a b}} = (a^{\log_a c})^{\frac{1}{\log_a b}} = c^{\log_b a}$

3.2-3

证明等式（3.19）： $\lg(n!) = \Theta(n \lg n)$ 。并证明 $n! = \omega(2^n)$ 且 $n! = o(n^n)$ 。

根据斯特林近似公式：

$\lg(n!) = \lg \left(\sqrt {2 \pi n} \left(\frac{n}{e}\right)^2 \left( 1 + \Theta (\frac{1}{n}) \right) \right)$

$= \lg \sqrt{2 \pi n} + n \lg \frac{n}{e} + \lg \left( 1 + \Theta ( \frac{1}{n}) \right)$

$= \Theta(n \lg n)$

故， $\lg(n!) = \Theta(n \lg n)$ 。
$\lim \limits_{x \to \infty} \frac {\sqrt{2 \pi n} \left(\frac{n}{e}\right)^n} {2^n} = \lim \limits_{x \to \infty} \sqrt{2 \pi n} \left(\frac{2n}{e}\right)^n = \infty$

故， $\forall c > 0, \exists n_0 > 0$ ，使得对所有的 $n \geq n_0$ ，有 $0 \leq c 2^n < n!$ ，故 $n! = \omega(2^n)$ 。
$\lim \limits_{x \to \infty} \frac {\sqrt{2 \pi n} \left(\frac{n}{e}\right)^n} {n^n} = \lim \limits_{x \to \infty} \frac {\sqrt{2 \pi n}} {e^n} = 0$

故， $\forall c > 0, \exists n_0 > 0$ ，使得对所有的 $n \geq n_0$ ，有 $0 \leq n! < c n^n$ ，故 $n! = o(n^n)$ 。

3.2-4*

函数 $\lceil \lg n \rceil !$ 多项式有界吗？函数 $\lceil \lg \lg n \rceil !$ 多项式有界吗？

多项式有界，即随着 $n$ 增大，一直满足： $f(n) \leq c n^k$

两边同时取对数： $\lg f(n) \leq \lg c + k \lg n$

也就是若 $\lg f(n) = O(\lg n)$ ，则函数 $f(n)$ 多项式有界。

对于 $f(n) = \lceil \lg n \rceil !$ ，有： $\lg(\lceil \lg n \rceil !) = \Theta(\lceil \lg n \rceil \lg \lceil \lg n \rceil) = \omega(\lg n) \neq O(\lg n)$ ，故函数 $\lceil \lg n \rceil !$ 不是多项式有界的。

对于 $f(n) = \lceil \lg \lg n \rceil !$ ，有：

$\lg(\lceil \lg \lg n \rceil !) = \Theta(\lceil \lg \lg n \rceil \lg \lceil \lg \lg n \rceil) = o(\lg \lg n \lg \lg n) = o(\lg^2 \lg n) = o(\lg n) = o(n)$

其中， $\lg^b n = o(n^a), \forall a> 0$

故函数 $\lceil \lg \lg n \rceil !$ 是多项式有界的。

3.2-5*

如下两个函数中，哪一个渐进更大些： $\lg(\lg^* n)$ 还是 $\lg^*(\lg n)$ ？

设 $2^{2^{2^{2...}}}(i 个 2)，\lg (\lg^* n) = \lg i，\lg^*(\lg n) = i - 1$ 。

又 $\lg^b n = o(n^a)$ ，故 $\lg^*(\lg n)$ 渐进更大一些。

3.2-6

证明：黄金分割率 $\phi$ 极其共轭数 $\hat{\phi}$ 都满足方程 $x^2 = x + 1$ 。

$\phi^2 - \phi - 1 = (\frac{1 + \sqrt{5}}{2})^2 - \frac{1 + \sqrt{5}}{2} - 1 = \frac{1 + 5 + 2 \sqrt{5} - 2 - 2 \sqrt{5} - 4}{4} = 0$

$\phi^2 - \phi - 1 = (\frac{1 - \sqrt{5}}{2})^2 - \frac{1 - \sqrt{5}}{2} - 1 = \frac{1 + 5 - 2 \sqrt{5} - 2 + 2 \sqrt{5} - 4}{4} = 0$

3.2-7

用归纳法证明：第 $i$ 个斐波那契数满足等式 $F_i = \frac{\phi^i - \hat{\phi}}{\sqrt{5}}$ ，其中 $\phi$ 是黄金分割率且 $\hat{\phi}$ 是其共轭数。

当 $i = 0， i = 1$ 时：

$\frac{\phi^0 - \hat{\phi}^0}{\sqrt{5}} = \frac{1 - 1}{2 \sqrt{5}} = 0 = F_0$

$\frac{\phi^1 - \hat{\phi}^1}{\sqrt{5}} = \frac{1 + \sqrt{5} - 1 + \sqrt{5}}{2 \sqrt{5}} = 1 = F_1$

另可证：

$\phi^2 = \frac{(1 + \sqrt{5})^2}{2^2} = \frac{3 + \sqrt{5}}{2} = \phi + 1$

$\hat{\phi}^2 = \frac{(1 - \sqrt{5})^2}{2^2} = \frac{3 - \sqrt{5}}{2} = \hat{\phi} + 1$

假设 $i = n, i = n + 1$ 时，满足等式。则：

$F_{n + 2} = F_{n + 1} + F_n = \frac{\phi^{n + 1} - \hat{\phi}^{n + 1}}{\sqrt{5}} + \frac{\phi^n - \hat{\phi}^n}{\sqrt{5}} = \frac{\phi^n(\phi + 1) - \hat{\phi}^n(\hat{\phi} + 1)}{\sqrt{5}} = \frac{\phi^n \phi^2 - \hat{\phi}^n \hat{\phi}^2}{\sqrt{5}} = \frac{\phi^{n + 2} - \hat{\phi}^{n + 2}}{\sqrt{5}}$

3.2-8

证明： $k \ln k = \Theta(n)$ 蕴含着 $k = \Theta \left(\frac{n}{\ln n} \right)$ 。

由对称性： $f(n) = \Theta(g(n))$ 当且仅当 $g(n) = \Theta(f(n))$ ，得：

$k \ln k = \Theta(n) \Rightarrow n = \Theta(k \ln k)$

$\ln n = \Theta(\ln k + \ln \ln k) = \Theta(\ln k)$

两者相除，有：

$\frac{n}{\ln n} = \Theta(\frac{k \ln k}{\ln k}) = \Theta(k)$

又由对称性，得： $k = \Theta(\frac{n}{\ln n})$ 。

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念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