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

看板Grad-ProbAsk作者 (fmtshk)時間6年前 (2019/07/14 02:49), 編輯推噓2(2推 0噓 9→)
留言11則, 4人參與, 6年前最新討論串1/1
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)有點障礙 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 118.167.122.167 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1563043799.A.ED7.html
推
07/14 07:58, 6年前 , 1F
你怎麼確定(lgn)!有lgn個？ 他是對數的階層，應該沒辦法
07/14 07:58, 1F
→
07/14 07:58, 6年前 , 2F
直接展開喔 然後stirling number就是把那個變數n帶logn進
07/14 07:58, 2F
→
07/14 07:58, 6年前 , 3F
去，然後你說有障礙的-log e那邊是不是卡在a^logb可以換
07/14 07:58, 3F
→
07/14 07:58, 6年前 , 4F
成b^loga
07/14 07:58, 4F
→
07/14 09:06, 6年前 , 5F
07/14 09:06, 5F
推
07/14 09:06, 6年前 , 6F
07/14 09:06, 6F
→
07/14 14:53, 6年前 , 7F
好像也是，原本我是想說3！是1乘到3，所以logn就乘到logn
07/14 14:53, 7F
→
07/14 14:53, 6年前 , 8F
，沒想清楚@@
07/14 14:53, 8F
→
07/14 14:53, 6年前 , 9F
我在研究一下，謝謝
07/14 14:53, 9F
→
07/17 09:28, 6年前 , 10F
我上傳的圖片有錯的地方嗎為何大家都點不喜歡╯-___-)
07/17 09:28, 10F
→
07/17 09:28, 6年前 , 11F
╯~═╩══╩═
07/17 09:28, 11F
‣ 更多 fmtshk 的文章
文章代碼(AID): #1TAYVNxN (Grad-ProbAsk)