※ 引述《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)