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