[理工] DS time complexity

看板Grad-ProbAsk作者 (古月小楓)時間12年前 (2011/12/05 20:24), 編輯推噓2(2推 0噓 1→)
留言3則, 3人參與, 最新討論串1/1
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
推
12/05 20:27, , 1F
積分
12/05 20:27, 1F
推
12/05 20:41, , 2F
Σ1/n ≒ log n
12/05 20:41, 2F
→
12/05 22:08, , 3F
多謝! 我懂了
12/05 22:08, 3F
‣ 更多 SiriusCloud 的文章
文章代碼(AID): #1EtBVt-e (Grad-ProbAsk)