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

[mqazz1 (無法顯示)]

※ 引述《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
→ metalalive:原來如此,沒想到是調和級數 orz 謝謝mqazz1大!!