作者fmtshk (fmtshk)
看板Grad-ProbAsk
标题[理工] 资料结构_(log n)!的复杂度
时间Sun Jul 14 02:49:57 2019
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)有点障碍
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 118.167.122.167 (台湾)
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1563043799.A.ED7.html
1F:推 mistel: 你怎麽确定(lgn)!有lgn个? 他是对数的阶层,应该没办法 07/14 07:58
2F:→ mistel: 直接展开喔 然後stirling number就是把那个变数n带logn进 07/14 07:58
3F:→ mistel: 去,然後你说有障碍的-log e那边是不是卡在a^logb可以换 07/14 07:58
4F:→ mistel: 成b^loga 07/14 07:58
7F:→ fmtshk: 好像也是,原本我是想说3!是1乘到3,所以logn就乘到logn 07/14 14:53
8F:→ fmtshk: ,没想清楚@@ 07/14 14:53
9F:→ fmtshk: 我在研究一下,谢谢 07/14 14:53
10F:→ tayashot: 我上传的图片有错的地方吗为何大家都点不喜欢╯-___-) 07/17 09:28
11F:→ tayashot: ╯~═╩══╩═ 07/17 09:28