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