› 看板 Grad-ProbAsk 關於我們 聯絡資訊
作者kyuudonut (CC)
看板Grad-ProbAsk
標題[理工] [資結] (loglogn)! 是否 poly-bounded
時間Sun Jul 31 17:34:28 2016
各位午安 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
推 prelude0390: http://i.imgur.com/Tc3JgaM.jpg 07/31 19:39
→ prelude0390: 參考一下 07/31 19:39
推 a19930301: ↑結果是對的，過程是錯的 07/31 20:41
→ a19930301: 取log你階層那符號應該要在括號裡(要用stirting) 07/31 20:43
推 prelude0390: 我寫不夠詳細 07/31 21:13
→ prelude0390: (lglg n)! 取log = lg( (lglg n)! ) 07/31 21:13
推 a19930301: 你寫這樣，後面會變(loglogn!)log(loglogn!)←變更複雜 07/31 21:39
推 a19930301: 當公式背就好，我覺得資結不會考證這個(這變純數了吧) 07/31 21:43
推 prelude0390: http://i.imgur.com/Z4PUdNw.jpg 07/31 21:58
→ tomdog12345: f(n):polynomially bounded iff f(n)=O(n^k) ,iff 07/31 22:08
→ tomdog12345: lgf(n)=O(lgn) 07/31 22:08
→ tomdog12345: 這是我上課抄的定義 07/31 22:09
謝謝，我怎麼沒抄到QQ
→ prelude0390: 樓上正解 07/31 22:39
→ prelude0390: 若一個t(n)是poly-bounded 07/31 22:39
→ prelude0390: 也就是說t(n)的time complexity會被 bound在 polynom 07/31 22:39
→ prelude0390: ial time裡 07/31 22:39
→ prelude0390: http://i.imgur.com/92M5WcI.jpg 07/31 22:41
謝謝提供關鍵字! ※ 編輯: kyuudonut (220.132.251.85), 07/31/2016 23:31:21