作者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/cn.aspx?n=bbs/Prob_Solve/M.1508048737.A.496.html
1F：推 michael47: 感谢告知，没有反应过来，我将原文删了，不想浪费资源 10/15 14:27
2F：推 oToToT: 刚开始学的时候也会没想到换底让他变常数XDD 10/17 23:16