[理工] (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
蛮好奇的 像是这种题目要怎么写出他的等级应该也只能说比什么大或是比什么小而已吧没办法写出确切的等级

Links booklink

Contact Us: admin [ a t ] ucptt.com