PTT
Submit
Submit
选择语言
正體中文
简体中文
PTT
Grad-ProbAsk
[理工] (log(logn))!的时间复杂度
楼主:
cschenptt
(chen)
2018-11-09 00:39:58
题目:(log(logn))!
法一
log(n!)=log(n*(n-1)*...*1)
=logn+log(n-1)+....+log(1)
<=logn+logn+...+logn (共有n项)
=n*logn
作者:
wilson50101
(我觉得我还不错啊)
2018-11-09 00:42:00
你取log法是拿来比大小的 不是拿来推等级的
https://i.imgur.com/PZgLfdI.jpg
应该是像图片右边这样 用Stirling应该没办法知道确切值可是可以知道介于哪个等级之间
作者:
skyHuan
(Huan)
2018-11-09 01:27:00
https://imgur.com/l9M1Fl3.jpg
我自己是只有记夹挤,取log也可以用夹挤看,Stirling理论上应该是推得出来但很容易代错,不然可以先把Stirling的n都换成t再代你要的loglogn进去比较不会看错(?你法二也代错了(log(logn))!=(loglogn)!=loglogn*[(loglogn)-1]*[(loglogn)-2]*..*2*1以上是取log后的复杂度,如果要求原本的复杂度会在对数跟多项式之间,如下图证明(5)
https://imgur.com/WswXoUX.jpg
作者:
wilson50101
(我觉得我还不错啊)
2018-11-09 23:45:00
蛮好奇的 像是这种题目要怎么写出他的等级应该也只能说比什么大或是比什么小而已吧没办法写出确切的等级
继续阅读
[理工] 离散 问题
liu1030
[理工] 离散 递回关系式 例7
QoGIVoQ
Re: [理工] 计组 张凡(下)P.220 RAID
Willywangkaa
[理工] 计组 101交大资联 ALU
Chen334
[理工] os 题库班讲义 interrupt
wilson50101
资料结构 external sorting
paralyzation
[理工] OS 题库第一章
magic83v
[理工] 计组jump指令目的位址计算
wacheck
[理工] 线代 102交大 SVD问题
magic83v
[理工] 离散-关系
Dora5566
Links
booklink
Contact Us: admin [ a t ] ucptt.com