作者OwTaingJune (機械加魯魯)
看板Grad-ProbAsk
標題[理工] 時間複雜度一題
時間Tue Jan 22 21:05:51 2019
T(n)=2T(n/2)+n/logn
https://imgur.com/a/psPpdkY
我不太理解為什麼紅色方塊的部分會變成綠色方塊的部分
1/(log (n/2^i) ) = 1/ (logn-log2^i)
如果要變成上述綠色方塊的部分，還需要什麼條件呢?
謝謝
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 36.225.121.51
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Grad-ProbAsk/M.1548162355.A.8FB.html
1F：→ rockieloser: log運算而已 01/22 21:08
2F：→ rockieloser: log(n/2^i) = log(n) - log(2^i) (log2^i = i) 01/22 21:18
您好，log(2^i)=i這部分請問是2為底嗎?
※ 編輯: OwTaingJune (36.225.121.51), 01/22/2019 21:22:33
※ 編輯: OwTaingJune (36.225.121.51), 01/22/2019 21:23:25
3F：→ rockieloser: 是 01/22 21:27
好的，謝謝您！
※ 編輯: OwTaingJune (36.225.121.51), 01/22/2019 22:05:17