Re: [理工] [資結] (loglogn)! 是否 poly-bounded

[h42318 (五兩三)]

定義：假設f(n)為polynomially bounded則代表f(n)=O(n^k)，
接著對左右兩邊取log變成：log(f(n))=O(logn) (意思就是log(f(n))<=k*logn)
結論：對f(n)取log只要小於k*logn, for all k屬於常數，就是polynomially bounded

題目：(loglogn)!是polynomially bounded嗎？
(技巧：使用log(n!)=n*logn的性質)

所以，log((loglogn)!)=loglogn*log(loglogn)<=loglogn*loglogn<=O(logn)
所以會是polynomially bounded!

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 110.30.200.84
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1469974161.A.A00.html
※ 編輯: h42318 (110.30.200.84), 07/31/2016 22:14:30
推 kyuudonut: 大感謝!! 那關於 (loglogn)^2 <= O(logn) 成立這件事
→ kyuudonut: 我是在取一次log 2log(loglogn) vs loglogn 做比較
→ kyuudonut: 所以 (loglogn)^2 比logn差一個等級 不知道這樣理解
→ kyuudonut: 是否正確?
沒錯！可以這樣比較，或者也可以直接用看的：隨便找個n例如4,8,16代進去看看就知道
(loglogn)^2必定小於c*logn, for all c屬於常數
※ 編輯: h42318 (110.30.200.84), 08/01/2016 00:16:58
推 a19930301: 可能老師不一樣，我筆記是用斯特靈公式來解
我筆記上兩個方法都有！用stirling公式也可以解的出來會小於多項式時間
※ 編輯: h42318 (110.30.200.84), 08/01/2016 00:49:06
→ prelude0390: 我的筆記是兩種解法都有
p大正解
※ 編輯: h42318 (110.30.200.84), 08/01/2016 00:50:54
※ 編輯: h42318 (110.30.200.84), 08/01/2016 00:51:47