[理工] 資料結構 growth rate問題 for0423 PTT批踢踢實業坊

作者: for0423 (屬於金牛的妳) 2018-04-02 14:18:21

https://i.imgur.com/9pfqVVt.jpg
洪逸上課提到的
式子左邊是對數乘對數右邊是常數乘對數
對數的等級比常數高
為什麼是右邊>左邊不是左邊>右邊啊

作者: Azlar911 (Azlar) 2018-04-02 14:42:00

對數比常數高沒錯可是這題後面的對數等級不一樣多log一次會降很多

作者: TMDTMD2487 (ㄚ冰) 2018-04-02 15:23:00

左邊是對數的對數乘上對數的對數的對數

作者: rio35 (rio) 2018-04-03 01:31:00

我的理解方式比較蠢...右邊是常數乘上對數，那就不是單純常數了，而是成為對數的形狀囉

作者: kcilao110779 (kcilao) 2018-04-03 05:04:00

https://imgur.com/PPzDDDl.jpg這我上課抄的給你參考前面有個定理提到 f(n)取log後=O(logn)的話此式就是polynomial bounded

作者: for0423 (屬於金牛的妳) 2018-04-03 14:07:00

我明白了謝謝大家

繼續閱讀