[理工] 资料结构 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

我明白了谢谢大家

继续阅读