推 jerry771210:我本來也是要這樣切 可是跳過nlgn了 留這篇就好摟XD 03/18 08:40
個人的想法是,既然要證明 θ(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)