log(n!)是否等于Θ(n·log(n))？

Question

我需要证明 log(n!) = Θ(n·log(n))。

提示说我应该用 nⁿ 来证明上界，并用 (n/2)^(n/2) 来证明下界。这对我来说似乎并不是那么直观。为什么会这样呢？我确实可以看到如何将 nⁿ 转换为 n·log(n)（即在等式两边取对数），但这有点像倒推。

应该采取什么正确的方法来解决这个问题？我应该画递归树吗？这个问题没有递归，所以这似乎不是一个可行的方法。

- Mark

---

你应该真正地写出它，包括“当n -> ∞时”。 - MartW

有趣的练习：使用类似的技巧展示调和级数 1/1 + 1/2 + 1/3 + 1/4 + ... 发散到无穷大。 - Yoo

这个不应该放在cs.stackexchange.com吗？ - CodyBugstein

@CodyBugstein，cs.stackexchange.com在提问时还不存在。 - MrMartin

Answer 1

请记住

log(n!) = log(1) + log(2) + ... + log(n-1) + log(n)

你可以通过以下方式得到上限：

log(1) + log(2) + ... + log(n) <= log(n) + log(n) + ... + log(n)
                                = n*log(n)

您可以在舍弃求和的前一半后，执行类似的操作来获得下限：

log(1) + ... + log(n/2) + ... + log(n) >= log(n/2) + ... + log(n) 
                                       = log(n/2) + log(n/2+1) + ... + log(n-1) + log(n)
                                       >= log(n/2) + ... + log(n/2)
                                        = n/2 * log(n/2) 

- Mick

---

这是一个非常漂亮的上界证明：log(n!) = log(1) + ... + log(n) <= n log(n) => log(n!) = O(n log n)。然而，为了证明下界（从而得出大O与大Ω），您可能需要使用斯特林公式的近似值。 - Mehrdad Afshari

你不需要使用斯特林公式求解一个下界。log(n!) = log(1) + ... + log(n) >= log(n/2) + ... + log(n) >= n/2 * log(n/2) = Omega(n log n)。 - Keith Randall

@Keith：我还不太明白，请问能否有人在“log(n/2) + ... + log(n)”的“...”部分为我解释一下更多术语？谢谢！ - j_random_hacker

@j_random_hacker 说的是 log(n!) 的一部分，即 log(n/2) + log(n/2 + 1) + ... + log(n - 1) + log(n)。实际上，我刚刚阅读了这个问题并且看到提示已经在问题中给出。基本上，(n/2)^(n/2) <= n! <= n^n => log((n/2)^(n/2))<=log(n!)<=log(n^n) => Θ(n/2 * log(n/2))<=log(n!)<=Θ(n*log(n))。 - Mehrdad Afshari

这个解释与已接受的答案类似，但更加详细：http://www.mcs.sdsmt.edu/ecorwin/cs372/handouts/theta_n_factorial.htm - gayavat

Answer 2

我意识到这是一个很老的问题，并且有一个被接受的答案，但是这些答案都没有使用提示所提出的方法。

这是一个非常简单的论点:

n! (= 1*2*3*...*n)是n个小于或等于n的数字的乘积。因此，它比所有等于n的n个数字的乘积n^n要小。

在n!中，一半的数字（即n/2个数字）大于或等于n/2。因此，它们的乘积大于所有等于n/2的n/2个数字的乘积；即(n/2)^(n/2)。

通过取对数可以证明结果。

- Nemo

---

这其实与被接受的答案中的对数版本相同，只是在之后而不是之前进行对数运算（然而，它更清晰地使用了提示）。 - hugomg

这与被接受的答案有何不同？ - Harsh

@Harsh请检查已接受答案的编辑历史记录，并将时间戳与此答案进行比较。 - Nemo

Answer 3

很抱歉，我不知道如何在stackoverflow上使用LaTeX语法。

- Gilfoyle

---

这是一个很好的解释！我能够理解直到第七步，但是在第七步和第八步之间发生的数学魔法我无法理解... :-( - Oliver

第7步的论证基本上是，右边第一项是支配项，因此log(n!)可以近似为nlog(n)，或者说它的阶数为nlog(n)，这是用大O符号O(n*log(n))表示的。 - Gilfoyle

@Z3d4s，步骤7-8的转换是在说nlogn == log(n^n)，为了展示这个界限，你可以说第一项总是大于第二项，你可以检查任何更大的值，而且为了表达大O复杂度，我们将始终采取所有支配项中的最大项。因此，nlogn对大O时间有贡献。 - Shiv Prakash

@rsonx 这是两者兼备的 - 例如，请参见被接受的答案。关于{一些积极但非主导术语} - 实际上，所有乘法元素都小于1，因此乘积也小于1。 log将其带到负值，因此渐近结果实际上是O（nlogn） - {something}。仍然需要证明该“something”在渐近意义下与nlogn相比是微不足道的 - 而这个答案并没有提供它。这不会影响大O，但可能会影响Omega。无论如何，这是过度复杂化了，可以看看其他答案。 - SomeWittyUsername

基本上对于n->∞，(1/n) -> 0。因此(1 - (k/n)) -> 1，因此乘积项的对数趋向于0。 - angshuk nag

Answer 4

参见斯特林近似公式:

ln(n!) = n*ln(n) - n + O(ln(n))

其中最后两项比第一项不重要。

- dsimcha

Answer 5

对于下界，

lg(n!) = lg(n)+lg(n-1)+...+lg(n/2)+...+lg2+lg1
       >= lg(n/2)+lg(n/2)+...+lg(n/2)+ ((n-1)/2) lg 2 (leave last term lg1(=0); replace first n/2 terms as lg(n/2); replace last (n-1)/2 terms as lg2 which will make cancellation easier later)
       = n/2 lg(n/2) + (n/2) lg 2 - 1/2 lg 2
       = n/2 lg n - (n/2)(lg 2) + n/2 - 1/2
       = n/2 lg n - 1/2

lg(n!) >= (1/2) (n lg n - 1)

将两个边界结合起来：

1/2 (n lg n - 1) <= lg(n!) <= n lg n

通过选择大于(1/2)的下边界常数，我们可以弥补括号内的-1。

因此，lg(n!) = Theta(n lg n)

- Vivek Anand Sampath

---

这种扩展的推导是必要的，因为 "something" >= n/2 * lg(n/2) 并不等于之前评论中提到的 omega(n lg n)。 - Vivek Anand Sampath

这应该写成“一个小于（1/2）的常数”，因为我们正在尝试找到一个下限。任何小于（1/2）的常数c，最终都会使得cnlogn <= (1/2)n*logn-(1/2)n，对于足够大的n。 - Matthew

Answer 6

谢谢，我认为你的回答很有说服力，但在我的情况下，我必须使用Θ属性：

log(n!) = Θ(n·log n) =>  log(n!) = O(n log n) and log(n!) = Ω(n log n)

为了验证我发现的问题，我找到了这个网站，其中详细解释了整个过程：http://www.mcs.sdsmt.edu/ecorwin/cs372/handouts/theta_n_factorial.htm

- WyrmxD

Answer 7

在Mick Sharpe离开您的地方继续帮助您：

它的推导非常简单：参见http://en.wikipedia.org/wiki/Logarithm -> 群论

log(n!) = log(n * (n-1) * (n-2) * ... * 2 * 1) = log(n) + log(n-1) + ... + log(2) + log(1)

将n视为无限大。 无限大减一是什么？ 或者减二？等等。

log(inf) + log(inf) + log(inf) + ... = inf * log(inf)

然后将inf视为n。

- Pindatjuh

---

我不同意这个观点，因为按照这个逻辑，可以得出n = O(n!)。根据你的说法，log(n!) = inf * log(inf)。"把n想象成无限大"。那么log(无穷大)等于什么？无穷大。因此，inf * log(inf)就是无穷大。另一方面，n是n的平方根乘以自身。当n变得无限大时，平方根也会变得无限大，所以你得到了无穷大乘以无穷大，结果还是无穷大。无穷大等于无穷大：证毕。 - benjixinator

Answer 8

瑞方近似法 可能对你有帮助。它在处理与阶乘有关的大量数字（例如10^10及以上）的问题时非常有用。

- user302520

Answer 9

这可能会有所帮助：

eln(x) = x

和

(lm)n = lm*n

- Anycorn

---

实际上，那是错误的：1^(m^n) ≠ 1^(m*n)正确的应该是(1^m)^n = 1^(m*n) - Pindatjuh

在上面的评论中，我是指使用 L 而不是 1。 - Pindatjuh

他没有写1^(m^n)，他写的是(l^m)^n。 - CodyBugstein

@CodyBugstein：问题已经被修复，你在多年后评论时错误已经隐藏在历史记录中。 - Ben Voigt

Answer 10

如果你重新构思这个问题，你可以用微积分来解决！这个方法最初是通过Arthur Breitman向我展示的https://twitter.com/ArthurB/status/1436023017725964290。

首先，你要对log(x)从1到n进行积分，结果是n*log(n) - n + 1。这证明了一个紧密的上界，因为log是单调的，对于每个点n，从n到n+1的log(n)的积分大于log(n) * 1。你可以类似地使用log(x-1)来构造下界，因为对于每个点n，1*log(n)大于从x=n-1到n的log(x)的积分。从0到n-1的log(x)的积分是(n-1)*(log(n-1) - 1)，或者n log(n-1) - n - log(n-1) + 1。

这些约束非常紧密！

- Jeremy Rubin