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

看板Grad-ProbAsk作者 (CC)時間9年前 (2016/07/31 17:34), 9年前編輯推噓6(6推 0噓 11→)
留言17則, 3人參與, 最新討論串1/2 (看更多)
各位午安 PTT終於能上惹 想請問標題 "(loglogn)! 是否為 poly-bounded?" 怎麼證? 我當時筆記抄的現在已經看不懂了... 大致上能理解成 取 log 後跟 n 和 (logn)^2 取log做比較 可以落在兩者之間 不知道有沒有人方便提供比較詳細的證明或筆記截圖呢 > < 另外不太清楚 poly-bounded 的定義 (餵狗也找不到@@) 是只要 polynomial time 以下(含) 都能夠算是 poly-bounded 嗎? 謝謝 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 220.132.251.85 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1469957671.A.5C5.html
推
07/31 19:39, , 1F
07/31 19:39, 1F
→
07/31 19:39, , 2F
參考一下
07/31 19:39, 2F
推
07/31 20:41, , 3F
↑結果是對的，過程是錯的
07/31 20:41, 3F
→
07/31 20:43, , 4F
取log你階層那符號應該要在括號裡(要用stirting)
07/31 20:43, 4F
推
07/31 21:13, , 5F
我寫不夠詳細
07/31 21:13, 5F
→
07/31 21:13, , 6F
(lglg n)! 取log = lg( (lglg n)! )
07/31 21:13, 6F
推
07/31 21:39, , 7F
你寫這樣，後面會變(loglogn!)log(loglogn!)←變更複雜
07/31 21:39, 7F
推
07/31 21:43, , 8F
當公式背就好，我覺得資結不會考證這個(這變純數了吧)
07/31 21:43, 8F
推
07/31 21:58, , 9F
07/31 21:58, 9F
→
07/31 22:08, , 10F
f(n):polynomially bounded iff f(n)=O(n^k) ,iff
07/31 22:08, 10F
→
07/31 22:08, , 11F
lgf(n)=O(lgn)
07/31 22:08, 11F
→
07/31 22:09, , 12F
這是我上課抄的定義
07/31 22:09, 12F
謝謝，我怎麼沒抄到QQ
→
07/31 22:39, , 13F
樓上正解
07/31 22:39, 13F
→
07/31 22:39, , 14F
若一個t(n)是poly-bounded
07/31 22:39, 14F
→
07/31 22:39, , 15F
也就是說t(n)的time complexity會被 bound在 polynom
07/31 22:39, 15F
→
07/31 22:39, , 16F
ial time裡
07/31 22:39, 16F
→
07/31 22:41, , 17F
07/31 22:41, 17F
謝謝提供關鍵字! ※ 編輯: kyuudonut (220.132.251.85), 07/31/2016 23:31:21
‣ 更多 kyuudonut 的文章
文章代碼(AID): #1NdSOdN5 (Grad-ProbAsk)
‣ 更多 kyuudonut 的文章
文章代碼(AID): #1NdSOdN5 (Grad-ProbAsk)