log（n！）=Θ（n·log（n））吗？

  • Z时代
  • 2024-01-10
  • 分类：问答

我要证明 。

提示我应该用 表示上限，而用 表示下限。在我看来，这似乎并不那么直观。为什么会这样呢？我绝对可以看到如何将 转换为 （即，记录方程的两边），但这有点倒退。

解决这个问题的正确方法是什么？我应该画递归树吗？对此没有任何递归，因此这似乎不是一种可行的方法。

回答：

请记住

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)

以上是 log（n！）=Θ（n·log（n））吗？ 的全部内容， 来源链接： utcz.com/qa/425511.html

回到顶部