各位午安 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