[理工] 資料結構_(log n)!的複雜度

作者: fmtshk (fmtshk)   2019-07-14 02:49:57
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)有點障礙
作者: mistel (Mistel)   2019-07-14 07:58:00
你怎麼確定(lgn)!有lgn個? 他是對數的階層,應該沒辦法直接展開喔 然後stirling number就是把那個變數n帶logn進去,然後你說有障礙的-log e那邊是不是卡在a^logb可以換成b^loga
作者: jeff1ou (子毛)   2019-07-14 09:06:00
作者: tayashot (Taya)   2019-07-14 09:06:00
作者: fmtshk (fmtshk)   2019-07-14 14:53:00
好像也是,原本我是想說3!是1乘到3,所以logn就乘到logn,沒想清楚@@我在研究一下,謝謝
作者: tayashot (Taya)   2019-07-17 09:28:00
我上傳的圖片有錯的地方嗎為何大家都點不喜歡╯-___-)╯~═╩══╩═

Links booklink

Contact Us: admin [ a t ] ucptt.com