[理工] DS time complexity

[SiriusCloud (古月小楓)]

T(n) = T(n-1) + 1/n  , T(1) = 1


(sol)

T(n) = T(n - 1) + 1 / n

     = [T(n - 2) + 1 / (n - 1)] + 1 / n
             .
             .
             .
             .
     = T(1) + 1 / 2 + 1 / 3 + ...... + 1 /(n - 1) + 1 / n

(answer)

     = O(log n)
       ↑ 怎麼轉換的?

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 114.46.137.88
推 Byzantin:積分
推 simonjoker:Σ1/n ≒ log n
→ SiriusCloud:多謝! 我懂了