《算法導(dǎo)論》第三章 3.2（參考答案）

3.2 標(biāo)準(zhǔn)記號與常用函數(shù)

3.2-1

證明：若 $f(n)$ 和 $g(n)$ 是單調(diào)遞增的函數(shù)谢澈，則函數(shù) $f(n) + g(n)$ 和 $f(g(n))$ 也是單調(diào)遞增的；此外御板，若 $f(n)$ 和 $g(n)$ 是非負(fù)的锥忿，則 $f(n) * g(n)$ 是單調(diào)遞增的。

若 $f(n)怠肋、g(n)$ 單調(diào)遞增敬鬓，即對任意的 $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$ ；

即函數(shù) $f(n) + g(n)$ 和 $f(g(n))$ 也是單調(diào)遞增的杈抢。

若 $f(n)$ 和 $g(n)$ 是非負(fù)的数尿，則 $f(n_1) * g(n_1) - f(n_2) * g(n_2) \leq 0$ ；

故 $f(n) * g(n)$ 是單調(diào)遞增的惶楼。

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

又對數(shù)函數(shù)為嚴(yán)格遞增函數(shù)嫩实，故 $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)$ 。

根據(jù)斯特林近似公式：

$\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*

函數(shù) $\lceil \lg n \rceil !$ 多項(xiàng)式有界嗎镊尺？函數(shù) $\lceil \lg \lg n \rceil !$ 多項(xiàng)式有界嗎朦佩？

多項(xiàng)式有界，即隨著 $n$ 增大庐氮，一直滿足： $f(n) \leq c n^k$

兩邊同時(shí)取對數(shù)： $\lg f(n) \leq \lg c + k \lg n$

也就是若 $\lg f(n) = O(\lg n)$ 语稠，則函數(shù) $f(n)$ 多項(xiàng)式有界。

對于 $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)$ 仙畦，故函數(shù) $\lceil \lg n \rceil !$ 不是多項(xiàng)式有界的。

對于 $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$

故函數(shù) $\lceil \lg \lg n \rceil !$ 是多項(xiàng)式有界的。

3.2-5*

如下兩個(gè)函數(shù)中桃熄，哪一個(gè)漸進(jìn)更大些： $\lg(\lg^* n)$ 還是 $\lg^*(\lg n)$ 先口？

設(shè) $2^{2^{2^{2...}}}(i 個(gè) 2)型奥，\lg (\lg^* n) = \lg i瞳收，\lg^*(\lg n) = i - 1$ 。

又 $\lg^b n = o(n^a)$ 厢汹，故 $\lg^*(\lg n)$ 漸進(jìn)更大一些螟深。

3.2-6

證明：黃金分割率 $\phi$ 極其共軛數(shù) $\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$ 個(gè)斐波那契數(shù)滿足等式 $F_i = \frac{\phi^i - \hat{\phi}}{\sqrt{5}}$ 烫葬，其中 $\phi$ 是黃金分割率且 $\hat{\phi}$ 是其共軛數(shù)界弧。

當(dāng) $i = 0凡蜻， i = 1$ 時(shí)：

? $\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$

假設(shè) $i = n, i = n + 1$ 時(shí)，滿足等式垢箕。則：

? $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)$ 蘊(yùn)含著 $k = \Theta \left(\frac{n}{\ln n} \right)$ 划栓。

由對稱性： $f(n) = \Theta(g(n))$ 當(dāng)且僅當(dāng) $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})$ 。

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者

人面猴
序言：七十年代末帅掘，一起剝皮案震驚了整個(gè)濱河市委煤，隨后出現(xiàn)的幾起案子，更是在濱河造成了極大的恐慌修档，老刑警劉巖碧绞，帶你破解...
沈念sama閱讀 222,104評論 6贊 515
死咒
序言：濱河連續(xù)發(fā)生了三起死亡事件，死亡現(xiàn)場離奇詭異吱窝，居然都是意外死亡讥邻，警方通過查閱死者的電腦和手機(jī)，發(fā)現(xiàn)死者居然都...
沈念sama閱讀 94,816評論 3贊 399
救了他兩次的神仙讓他今天三更去死
文/潘曉璐我一進(jìn)店門癣诱，熙熙樓的掌柜王于貴愁眉苦臉地迎上來计维，“玉大人，你說我怎么就攤上這事撕予■昊蹋” “怎么了？”我有些...
開封第一講書人閱讀 168,697評論 0贊 360
道士緝兇錄：失蹤的賣姜人
文/不壞的土叔我叫張陵实抡，是天一觀的道長欠母。經(jīng)常有香客問我，道長吆寨，這世上最難降的妖魔是什么赏淌？我笑而不...
開封第一講書人閱讀 59,836評論 1贊 298
?港島之戀（遺憾婚禮）
正文為了忘掉前任，我火速辦了婚禮啄清，結(jié)果婚禮上六水，老公的妹妹穿的比我還像新娘。我一直安慰自己辣卒，他們只是感情好掷贾，可當(dāng)我...
茶點(diǎn)故事閱讀 68,851評論 6贊 397
惡毒庶女頂嫁案：這布局不是一般人想出來的
文/花漫我一把揭開白布。她就那樣靜靜地躺著荣茫，像睡著了一般想帅。火紅的嫁衣襯著肌膚如雪。梳的紋絲不亂的頭發(fā)上啡莉，一...
開封第一講書人閱讀 52,441評論 1贊 310
城市分裂傳說
那天港准，我揣著相機(jī)與錄音旨剥，去河邊找鬼。笑死浅缸，一個(gè)胖子當(dāng)著我的面吹牛轨帜，可吹牛的內(nèi)容都是我干的。我是一名探鬼主播衩椒，決...
沈念sama閱讀 40,992評論 3贊 421
雙鴛鴦連環(huán)套：你想象不到人心有多黑
文/蒼蘭香墨我猛地睜開眼阵谚，長吁一口氣：“原來是場噩夢啊……” “哼！你這毒婦竟也來了烟具？” 一聲冷哼從身側(cè)響起梢什，我...
開封第一講書人閱讀 39,899評論 0贊 276
萬榮殺人案實(shí)錄
序言：老撾萬榮一對情侶失蹤，失蹤者是張志新（化名）和其女友劉穎朝聋，沒想到半個(gè)月后嗡午，有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體，經(jīng)...
沈念sama閱讀 46,457評論 1贊 318
?護(hù)林員之死
正文獨(dú)居荒郊野嶺守林人離奇死亡冀痕，尸身上長有42處帶血的膿包…… 初始之章·張勛以下內(nèi)容為張勛視角年9月15日...
茶點(diǎn)故事閱讀 38,529評論 3贊 341
?白月光啟示錄
正文我和宋清朗相戀三年荔睹，在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了。大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片言蛇。...
茶點(diǎn)故事閱讀 40,664評論 1贊 352
活死人
序言：一個(gè)原本活蹦亂跳的男人離奇死亡僻他，死狀恐怖，靈堂內(nèi)的尸體忽然破棺而出腊尚，到底是詐尸還是另有隱情吨拗，我是刑警寧澤，帶...
沈念sama閱讀 36,346評論 5贊 350
?日本核電站爆炸內(nèi)幕
正文年R本政府宣布婿斥，位于F島的核電站劝篷，受9級特大地震影響，放射性物質(zhì)發(fā)生泄漏民宿。R本人自食惡果不足惜娇妓，卻給世界環(huán)境...
茶點(diǎn)故事閱讀 42,025評論 3贊 334
男人毒藥：我在死后第九天來索命
文/蒙蒙一、第九天我趴在偏房一處隱蔽的房頂上張望活鹰。院中可真熱鬧哈恰，春花似錦、人聲如沸志群。這莊子的主人今日做“春日...
開封第一講書人閱讀 32,511評論 0贊 24
一樁弒父案，背后竟有這般陰謀
文/蒼蘭香墨我抬頭看了看天上的太陽赖舟。三九已至蓬戚，卻和暖如春夸楣，著一層夾襖步出監(jiān)牢的瞬間宾抓，已是汗流浹背子漩。一陣腳步聲響...
開封第一講書人閱讀 33,611評論 1贊 272
情欲美人皮
我被黑心中介騙來泰國打工，沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留石洗，地道東北人幢泼。一個(gè)月前我還...
沈念sama閱讀 49,081評論 3贊 377
代替公主和親
正文我出身青樓，卻偏偏與公主長得像讲衫，于是被迫代替她去往敵國和親缕棵。傳聞我的和親對象是個(gè)殘疾皇子，可洞房花燭夜當(dāng)晚...
茶點(diǎn)故事閱讀 45,675評論 2贊 359