证明n!对于任何常数自然数p,不在O(n ^ p)中

Question

我该如何证明n!任何常数自然数p不在O(n ^ p)中？并且(nk)(n选择k)在O(n ^ p)中,对于所有k？

Answer 1

斯特林的近似说明了这一点

log (n!) = n log n - n + O(log n) = O(n log n)

但

log (n^p) = p log n = O(log n)

为了恒定p.显然n!增长速度快n^p,因此不是O(n^p).

Answer 2

你可以证明n!对于任何常数自然数p,不在O(n ^ p)中,通过显示你总是可以选择n(对于固定常数p),这样n! > n^p.

(为了得到一个想法,选择一些低的p值并绘制n!对n ^ p)

第二部分的推理遵循相同的路线.绑定(n选择k)然后使用第一部分.

提示:正如卡萨布兰卡所说,你可以使用斯特林的近似值