algorithm - 对于某个常数 c，阶乘(floor(log(n)))是大 O(n ^ c)吗？

Question

谁能解释一下阶乘(floor(log(n)))是否是某个常量 c 的大 O(n^c)？以及，如何证明以上答案？

Answer 1

没有。 Asymptotically, we have

floor(log n)! = Ω(((log n)/3)^log n)
              = Ω(e^(log((log n) / 3)) * log n)
              = Ω(n^(log log n - log 3))

指数 log log n - log 3 显然不在 O(1) 中。