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

看板Grad-ProbAsk作者 (五兩三)時間9年前 (2016/07/31 22:09), 9年前編輯推噓2(2推 0噓 4→)
留言6則, 3人參與, 最新討論串2/2 (看更多)
定義：假設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
推
07/31 23:32, , 1F
大感謝!! 那關於 (loglogn)^2 <= O(logn) 成立這件事
07/31 23:32, 1F
→
07/31 23:32, , 2F
我是在取一次log 2log(loglogn) vs loglogn 做比較
07/31 23:32, 2F
→
07/31 23:33, , 3F
所以 (loglogn)^2 比logn差一個等級 不知道這樣理解
07/31 23:33, 3F
→
07/31 23:33, , 4F
是否正確?
07/31 23:33, 4F
沒錯！可以這樣比較，或者也可以直接用看的：隨便找個n例如4,8,16代進去看看就知道 (loglogn)^2必定小於c*logn, for all c屬於常數 ※ 編輯: h42318 (110.30.200.84), 08/01/2016 00:16:58
推
08/01 00:33, , 5F
可能老師不一樣，我筆記是用斯特靈公式來解
08/01 00:33, 5F
我筆記上兩個方法都有！用stirling公式也可以解的出來會小於多項式時間 ※ 編輯: h42318 (110.30.200.84), 08/01/2016 00:49:06
→
08/01 00:49, , 6F
我的筆記是兩種解法都有
08/01 00:49, 6F
p大正解 ※ 編輯: h42318 (110.30.200.84), 08/01/2016 00:50:54 ※ 編輯: h42318 (110.30.200.84), 08/01/2016 00:51:47
‣ 更多 h42318 的文章
文章代碼(AID): #1NdWQHe0 (Grad-ProbAsk)
‣ 更多 h42318 的文章
文章代碼(AID): #1NdWQHe0 (Grad-ProbAsk)