是O((log n)!)多项式？

Question

我想找O((log n)!).我认为O((log n)!)并且O(n!)是平等的!因为我认为当n是无限的(log n)!并且n!是相等的.这是真的吗？如果是,我该怎么表明？如果不是O((log n)!)多项式？

Answer 1

我认为你的后续问题是是否(logn)!是多项式限制.这显然不是多项式本身.斯特林的近似给了我们

n!?en^[n+1/2]*e^(?n)

所以,

(log n)!?e(log n)^[1/2+log n]*e^(?log n)

现在 (log n)^log n=(e^loglogn)^logn=e^[(logn)?(loglogn)]

因此,增长的顺序是近似的 e^[(logn)(loglogn)?logn] =n^[(loglogn)?1]

遗憾的是,这不受任何多项式的限制,因为loglogn最终会超过任何正整数.

例如,比较(log n)!用n^2.

在n=e^10,(log n)!=3480,同时(e^10)2?4.85×108

在n=e^100,(log n)!?10157 ,同时e^200?1086