Re: [課業] 3/17 演算法
※ 引述《jerry771210 (嘿嘿嘿)》之銘言：
: ※ 引述《moonlights (NE子)》之銘言：
: : 今日作業：
: : (1) 課本 P. 86，題目4-4 的 a, c, f, g 四小題，
: : (2) 證明 （harmonic series）
: : n
: : Hn = Σ 1/i = θ(lg n)
: : i=1
: : ◎ 老師給的愛心小提示：
: : 1/1 + 1/2 + 1/2 + 1/4 + 1/4 + 1/4 + 1/4 + 1/8 + 1/8 + ...
: : < Hn = 1/1 + 1/2 + 1/3 + 1/4 + 1/5 + 1/6 + 1/7 + 1/8 + ...
: : > 1/1 + 1/2 + 1/4 + 1/4 + 1/8 + 1/8 + 1/8 + 1/8 + 1/10 + ...
個人的想法是,既然要證明 θ(lg n)
照定義的話 c1*lgn< Hn <c2*lgn ,c1.c2找的到值就ok了
最上面那行 1/1 + 1/2 + 1/2 + 1/4 + 1/4 + 1/4 + 1/4 + 1/8.....是lgn
如果我們把老師提示的第一行乘上1/2的話
1/2 + 1/4 + 1/4 + 1/8 + 1/8 + 1/8 + 1/8 + 1/8 +.........
這一定比Hn小了吧~
那麼c1就代1/2 c2代1就可以滿足 c1*lgn< Hn <c2*lgn 得證!?
--------------------------
經過建中哥的開導後,發現要先搞定lgn是怎麼出來的
後來想了一個比較不一樣的說法來說(借用了上一篇的圖)
以下是Merge sort所需時間的圖
T(n)
--------------n個時間
/ \
T(n/2) T(n/2)
----------n/2+n/2個時間
/ \ / \
T(n/4) ........
. -----------n/4+n/4+n/4+n/4個時間
所以樹的深度會有lgn層,而每層都要n個時間,所以Merge sort是nlgn
轉成數學式子就是
n + n/2 + n/2 + n/4 + n/4 + n/4 + n/4 +.........= nlgn
同除n就會變成上面那個式子了
1/1 + 1/2 + 1/2 + 1/4 + 1/4 + 1/4 + 1/4 + ..... = lgn
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 115.43.148.161
※ 編輯: Markseinn 來自: 115.43.148.161 (03/18 01:43)
※ 編輯: Markseinn 來自: 115.43.148.161 (03/18 02:32)
推
03/18 08:40, , 1F
03/18 08:40, 1F
討論串 (同標題文章)
完整討論串 (本文為第 4 之 4 篇)：
課業
2
2