為什麼這篇bounded中文鄉民發文收入到精華區：因為在bounded中文這個討論話題中，有許多相關的文章在討論，這篇最有參考價值！作者h42318 (五兩三)看板Grad-ProbAsk標題Re: [理工] [資結] (loglo...
定義：假設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) 成立這件事 07/31 23:32
→ kyuudonut: 我是在取一次log 2log(loglogn) vs loglogn 做比較 07/31 23:32
→ kyuudonut: 所以 (loglogn)^2 比logn差一個等級 不知道這樣理解 07/31 23:33
→ kyuudonut: 是否正確? 07/31 23:33
沒錯！可以這樣比較，或者也可以直接用看的：隨便找個n例如4,8,16代進去看看就知道(loglogn)^2必定小於c*logn, for all c屬於常數
※ 編輯: h42318 (110.30.200.84), 08/01/2016 00:16:58
推 a19930301: 可能老師不一樣，我筆記是用斯特靈公式來解 08/01 00:33
我筆記上兩個方法都有！用stirling公式也可以解的出來會小於多項式時間※ 編輯: h42318 (110.30.200.84), 08/01/2016 00:49:06
→ prelude0390: 我的筆記是兩種解法都有 08/01 00:49
p大正解※ 編輯: h42318 (110.30.200.84), 08/01/2016 00:50:54
※ 編輯: h42318 (110.30.200.84), 08/01/2016 00:51:47