[理工] 资料结构_(log n)!的复杂度

楼主: fmtshk (fmtshk)   2019-07-14 02:49:57
https://i.imgur.com/CR4gn2I.jpg
关于此题的(lg n)! 和 (lg n)^lgn
我原本以为它们两个是同类
https://i.imgur.com/NU4S1ci.jpg
我把(lg n)!算成如上图那样
哪里算错了吗?
https://i.imgur.com/e74VMci.jpg
前几页有看到用Stirling's formula算(lg n)!
但我看不太懂那结果,对那个(-log e)有点障碍
作者: mistel (Mistel)   2019-07-14 07:58:00
你怎么确定(lgn)!有lgn个? 他是对数的阶层,应该没办法直接展开喔 然后stirling number就是把那个变量n带logn进去,然后你说有障碍的-log e那边是不是卡在a^logb可以换成b^loga
作者: jeff1ou (子毛)   2019-07-14 09:06:00
作者: tayashot (Taya)   2019-07-14 09:06:00
楼主: fmtshk (fmtshk)   2019-07-14 14:53:00
好像也是,原本我是想说3!是1乘到3,所以logn就乘到logn,没想清楚@@我在研究一下,谢谢
作者: tayashot (Taya)   2019-07-17 09:28:00
我上传的图片有错的地方吗为何大家都点不喜欢╯-___-)╯~═╩══╩═

Links booklink

Contact Us: admin [ a t ] ucptt.com