作者darkgerm (黑駿)
看板Prob_Solve
標題Re: [問題]演算法教科書的big O的疑問
時間Sun Oct 15 14:25:33 2017
※ 引述《michael47 (hitman)》之銘言：
: 在Introduction to Algorithms, Third Edition裡面
: 作者：Thomas H. Cormen, Charles E. Leiserson...(略)
: 的Page 92，在講遞迴樹
: 為何O(c*n*log(以3/2為底)n) = O(n*lgn)？
: c是常數，lgn是log(以2為底)n
: 若是從c1*n*lgn <= c2*n*log(以3/2為底)n來看
: 小於c2*n*log(以3/2為底)n不是不一定小於c1*n*lgn？
: 請問我是哪裡認知有錯誤？感激不盡
(以下 log 沒標底的皆以 2 為底)
log x
b
跟據 log 換底公式 log x = ---------
a log a
b
c * n * log n
3/2
log n
= c * n * ---------
log 3/2
c
= --------- * n * log n
log 3/2
1
c
∵--------- 為常數
log 3/2
c
∴O(--------- * n * log n) = O(n * log n)
log 3/2
演算法裡其實充滿了數算，若不熟的話建意先補足
不然會讀的很吃力
--
光明 的背後 是 黑暗
黑暗 的背後 還是 黑暗
由此可知 黑暗 > 光明 Q.E.D.
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.113.235.116
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Prob_Solve/M.1508048737.A.496.html
1F：推 michael47: 感謝告知，沒有反應過來，我將原文刪了，不想浪費資源 10/15 14:27
2F：推 oToToT: 剛開始學的時候也會沒想到換底讓他變常數XDD 10/17 23:16