[理工] (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