[理工] 時間複雜度一題

[OwTaingJune (機械加魯魯)]

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://www.ptt.cc/bbs/Grad-ProbAsk/M.1548162355.A.8FB.html
→ rockieloser: log運算而已
→ rockieloser: log(n/2^i) = log(n) - log(2^i) (log2^i = i)
您好，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
→ rockieloser: 是
好的，謝謝您！
※ 編輯: OwTaingJune (36.225.121.51), 01/22/2019 22:05:17