证明n!对于任何常数自然数 p 都不在 O(n^p) 范围内
我怎样才能证明n!对于任何常数自然数 p 都不在 O(n^p) 范围内？ 对于所有 k，(nk)(n 在 O(n^p) 中选择 k) 吗？
How can I prove that n! is not in O(n^p) for any constant natural number p?
And is (n k)(n choose k) in O(n^p), for all k?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
你可以证明 n!对于任何常数自然数 p，都不在 O(n^p) 范围内，通过表明您始终可以选择 n（对于固定常数 p），因此
n! > n^p。（为了得到一个想法，选择 p 的一些低值并绘制 n! 与 n^p 的关系）
第二部分的推理遵循相同的思路。绑定（n 选择 k）然后使用第一部分。
提示：正如卡萨布兰卡指出的，您可以使用斯特林近似
You can prove that n! is not in O(n^p) for any constant natural number p, by showing that you can always choose n (for a fixed constant p), so that
n! > n^p.(to get an idea, pick a few low values of p and plot n! against n^p)
The reasoning for the second part follows the same lines. Bound (n choose k) and then use first part.
Hint: as Casablanca noted, you can use Stirling's approximation
编辑 (3/2011) - 仅使用简单微积分的更简单方法
显示 O(n!) 不等于 O(n^p) 的一种方法是比较 n! 的对数！与 n^p 的对数。
ln(n!) = sum(ln(i)) {i: 1 to n}
ln(n^p) = p*ln(n)
这似乎没有帮助，因为我们不知道日志会是。诀窍是通过使用 ln(i)di 从 1 到 n 的积分来计算下界。从
下图中可以看出，黑色的 ln(x) 小于蓝色的阶跃函数和。
假设 ln(i)di 的不定积分为 i*ln(i) - i + C ，我们可以从 1 到 n 积分得到：
n*ln(n) - n + 1 作为下界。
并且因为无法选择大于所有可能的 n 的 p：
O(pln(n)) < O(nln(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) 的图形）
Edit (3/2011) - easier method using only simple calculus
One way to show O(n!) does not equal O(n^p) is to compare the log of n! with the log of n^p.
ln(n!) = sum(ln(i)) {i: 1 to n}
ln(n^p) = p*ln(n)
That doesn't seem to help since we don't know what the sum of the logs would be. The trick is to calculate a lower bound by using the integral of ln(i)di from 1 to n
This can be seen in the image below that the ln(x) in black is less than the sum step function in blue.
Given that the indefinite integral of ln(i)di is i*ln(i) - i + C, we can integrate from 1 to n to get:
n*ln(n) - n + 1 as the lower bound.
And because no p can be chosen that is larger than all possible n:
O(pln(n)) < O(nln(n)), O(n^p) < O(n!)
note: integrating ln(n) to get an approximation to ln(n!) is the basis for Stirling's approximation. This is a rougher approximation and if you continue it by taking the anti-log: n! >= e*(n/e)^n, whereas Stirling's has sqrt(2*pi*n) instead of e.
Integrating from 1 to n+1 would give you an upper bound (the sum step function would fit inside the graph of ln(n))
斯特林近似表示，
但
对于常数
p。显然，n!的增长速度比n^p快，因此它不是O(n^p)。Stirling's approximation says that
But
for constant
p. Clearlyn!grows faster thann^pand hence it is notO(n^p).