作者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/cn.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