Re: [問題]演算法教科書的big O的疑問
看板Prob_Solve (計算數學 Problem Solving)作者darkgerm (黑駿)時間7年前 (2017/10/15 14:25)推噓2(2推 0噓 0→)留言2則, 2人參與討論串2/2 (看更多)
※ 引述《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://www.ptt.cc/bbs/Prob_Solve/M.1508048737.A.496.html
推
10/15 14:27,
7年前
, 1F
10/15 14:27, 1F
推
10/17 23:16,
7年前
, 2F
10/17 23:16, 2F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 2 之 2 篇)：
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
