[理工] 資結p21 bigO turbo1 PTT批踢踢實業坊

[理工] 資結p21 bigO

作者: turbo1 (turbo) 2019-12-07 12:40:14

各位大大你們好
小的想請問這一題是否是這樣算的?
前面的T(n)我有算出來了
課本的big-O範例我也有看懂
但是到了log的部分就不太會判斷
https://i.imgur.com/1NcyTaC.jpg

作者: zuchang (chang) 2019-12-07 14:59:00

其實你前半段可以不用寫你可以記結論就是log的底數不管多少在big O下都是同level 不過底數要大於1就是

作者: turbo1 (turbo) 2019-12-07 15:20:00

原來是這樣謝謝z大

作者: zuchang (chang) 2019-12-07 15:25:00

右半段可以寫成T(n)=T(n/k)+lgk，k=n時T(n)=T(1)+lgn 的形式比較好看

繼續閱讀

[理工] 105暨南OS（fork)!Aa841018 [理工] 資結空間複雜度energyy1104 [理工] 離散生成函數lucy35 [理工] 線代 4-52,53 精選範例2題jean20157 [理工] 資結tayashot [理工] 資結 104 清大mandychad [理工] 104交大 OS file systemdsa66253 [理工] 線代 99中央資工第13題ching4562 [理工] DS TREEAdonisLam [理工]離散圖論 104高雄資工AirComm

Contact Us: admin [ a t ] ucptt.com