各位午安 PTT終於能上惹
想請問標題
"(loglogn)! 是否為 poly-bounded?"
怎麼證?
我當時筆記抄的現在已經看不懂了...
大致上能理解成 取 log 後跟 n 和 (logn)^2 取log做比較
可以落在兩者之間
不知道有沒有人方便提供比較詳細的證明或筆記截圖呢 > <
另外不太清楚 poly-bounded 的定義 (餵狗也找不到@@)
是只要 polynomial time 以下(含) 都能夠算是 poly-bounded 嗎?
謝謝

http://i.imgur.com/Tc3JgaM.jpg參考一下

↑結果是對的，過程是錯的取log你階層那符號應該要在括號裡(要用stirting)

我寫不夠詳細(lglg n)! 取log = lg( (lglg n)! )

你寫這樣，後面會變(loglogn!)log(loglogn!)←變更複雜當公式背就好，我覺得資結不會考證這個(這變純數了吧)

f(n):polynomially bounded iff f(n)=O(n^k) ,ifflgf(n)=O(lgn)這是我上課抄的定義

樓上正解若一個t(n)是poly-bounded也就是說t(n)的time complexity會被 bound在 polynomial time裡http://i.imgur.com/92M5WcI.jpg