我如何证明 n! 对于任何常数自然数 p 都不在 O(n^p) 中吗？并且是 (nk)(n 选择 k) 在 O(n^p) 中，对于所有 k？
user497302
问问题
1233 次
3 回答
10
斯特林的近似表明
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)。
于 2010-11-07T01:02:47.900 回答
8
你可以证明 n! 对于任何常数自然数 p 都不在 O(n^p) 中，通过表明您始终可以选择 n（对于固定常数 p），因此n! > n^p.
（为了得到一个想法，选择一些 p 的低值并绘制 n！对 n^p）
第二部分的推理遵循相同的思路。绑定（n 选择 k）然后使用第一部分。
提示：正如卡萨布兰卡所指出的，您可以使用斯特林的近似值
于 2010-11-07T01:00:06.173 回答
2
编辑 (3/2011) - 仅使用简单微积分的更简单方法
显示 O(n!) 不等于 O(n^p) 的一种方法是比较 n 的对数！与 n^p 的对数。
ln(n!) = sum(ln(i)) {i: 1 到 n}
ln(n^p) = p*ln(n)
这似乎没有帮助，因为我们不知道日志的总和是多少。诀窍是通过使用 ln(i)di 从 1 到 n 的积分来计算下限
从下图中可以看出，黑色的 ln(x) 小于蓝色的 sum step function。
假设 ln(i)di 的不定积分是 i*ln(i) - i + C，我们可以从 1 到 n 积分得到：
n*ln(n) - n + 1 作为下限。
并且因为无法选择大于所有可能的 n 的 p：
O(p ln(n)) < O(n ln(n)), O(n^p) < O(n!)
注意：积分 ln(n) 以获得 ln(n!) 的近似值是斯特林近似值的基础。这是一个更粗略的近似值，如果您通过取反对数继续它：n！>= e*(n/e)^n，而斯特林的有 sqrt(2*pi*n) 而不是 e。
从 1 积分到 n+1 会给你一个上限（和阶跃函数将适合 ln(n) 的图形）
于 2010-11-07T02:06:49.127 回答