Re: [理工][algo][演算] 時間複雜度 , 不能以maste …

看板Grad-ProbAsk作者 (無法顯示)時間13年前 (2011/06/16 21:02), 編輯推噓0(0推 0噓 1→)
留言1則, 1人參與, 最新討論串2/2 (看更多)
※ 引述《metalalive (想玩音樂)》之銘言： : 97 交大資訊 : assume n<=2 , 解 tight asymptotic upper bound : T(n) = T(n-1) + 1/n : 解答是給 Θ(lgn) : 但我想不到過程 : 尤其是 1/x 部分要怎麼解 T(n) = T(n-1) + 1/2 = T(n-2) + 1/(n-1) + 1/n = ... = T(1) + 1/2 + 1/3 + ... + 1/n 這是一個調和級數 用積分去夾擠可證出 T(n) = Θ(lgn) -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 61.228.28.131
→
06/17 00:04, , 1F
原來如此,沒想到是調和級數 orz 謝謝mqazz1大!!
06/17 00:04, 1F
‣ 更多 mqazz1 的文章
文章代碼(AID): #1D-Vx_Zi (Grad-ProbAsk)
‣ 更多 mqazz1 的文章
文章代碼(AID): #1D-Vx_Zi (Grad-ProbAsk)