[理工] 時間複雜度一題

看板Grad-ProbAsk作者 (機械加魯魯)時間5年前 (2019/01/22 21:05), 5年前編輯推噓0(0推 0噓 3→)
留言3則, 1人參與, 5年前最新討論串1/1
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
→
01/22 21:08, 5年前 , 1F
log運算而已
01/22 21:08, 1F
→
01/22 21:18, 5年前 , 2F
log(n/2^i) = log(n) - log(2^i) (log2^i = i)
01/22 21:18, 2F
您好，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
→
01/22 21:27, 5年前 , 3F
是
01/22 21:27, 3F
好的，謝謝您！ ※ 編輯: OwTaingJune (36.225.121.51), 01/22/2019 22:05:17
‣ 更多 OwTaingJune 的文章
文章代碼(AID): #1SHnKpZx (Grad-ProbAsk)