[問題]演算法教科書的big O的疑問消失

看板Prob_Solve (計算數學 Problem Solving)作者時間7年前 (2017/10/14 20:53), 編輯推噓1(101)
留言2則, 1人參與, 最新討論串1/2 (看更多)
在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? 請問我是哪裡認知有錯誤?感激不盡 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.241.133.151 ※ 文章網址: https://www.ptt.cc/bbs/Prob_Solve/M.1507985599.A.17F.html

10/14 22:26, , 1F
Big-O 因為定義的關係差一個常數倍是可以當做沒差的
10/14 22:26, 1F

10/14 22:26, , 2F
用你的話來說, c2 是你找的, 你當然可以找個適當的值
10/14 22:26, 2F
文章代碼(AID): #1PuWY_5_ (Prob_Solve)
文章代碼(AID): #1PuWY_5_ (Prob_Solve)