log(n!) = Ω( n*log(n)) 的翻译是什么意思？

Question

log(n!) = Ω( n*log(n)) 的翻译是什么意思？

3

我知道这个。

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

并且

 n*log(n)= log(n) + log(n) + .... + log(n) or just adding log(n)'s  n times.

我可以把 n*log(n) 乘以什么常数使其小于 log(n!) 呢？

我读到了一些关于它是 n/2*log(n/2) 的解决方案。那是什么常数？是一半吗？

一个解决方案来自于这里。Is log(n!) = Θ(n·log(n))?

如果 C=1/2，那么它不就是 (n/2)*log(n) 吗？为什么 log 中的 n 变成了 n/2？

我知道 log 规则中的 log(a/b) = log a - log b。这个规则有帮助吗？

- Arrow

5

这个问题似乎不适合在这里讨论，它应该发表在math.stackexchange.com或cs.stackexchange.com上。 - Barmar

1

这个问题有一个类似的问题，但是它的解决方案我不理解。我会编辑我的帖子，加上链接。https://dev59.com/qXI95IYBdhLWcg3w7CfL - Arrow

我最近在这里写了一个简单的估算，使用了黎曼和梯形积分公式：(http://math.stackexchange.com/questions/689752) - Lutz Lehmann

3个回答

0

为了让amit的第一个答案更加基础:

考虑n!=1*2*3*...*(n-1)*n与其反向组合，即

   (n!)^2=(n)*(1*(n-1))*(2*(n-2))*...*((n-1)*1)*(n)

然后每个内积都允许进行以下估计

    k*(n-k)>=1*max(k,n-k)>=n/2

通过算术-几何平均数，或者仅仅是因为x*(1-x)在0和1的中间点1/2处最大，

    k*(n-k)<=((n-k)+k)/2)^2=(n/2)^2

将所有东西组合起来，我们得到：

    n*(n/2)^(n-1)*n <= (n!)^2 <= n*(n/2)^(2(n-1))*n

并且取对数并除以2

    (n+1)/2*log(n/2)+log(2) 
         <= log(n!) 
             <= n*log(n/2)+log(2)

这样，下限将具有 1/2*n*log(n) 的主导项，上限将具有 n*log(n) 的主导项。

- Lutz Lehmann

0

这不是一个简单的常数。我认为您正在考虑证明O(log(n!)) = O(n*log(n))，如果是这样，那么您需要使用Sterling's approximation。如果使用这个近似公式，您可以证明对于任何值c < 1，都应该存在一个值N，使得对于n > = N，c * n*log(n) < log(n!)。

- Ivaylo Strandjev

1

(1) 这个问题是关于Omega，而不是大O的。 (2) 没有必要得到精确（最紧）的常数，只需要展示这样一个常数存在即可，这相当简单。 - amit

@amit 我看到这是关于omega的，但我认为我们需要最紧密的。也许我误解了问题？ - Ivaylo Strandjev

根据我对问题的理解，@MattC想知道如何证明log(n!)属于Omega(nlogn)，因此您只需要展示这样的常数存在即可。 - amit

我假设这里有一个常数来自于这个线程（我不理解）https://dev59.com/qXI95IYBdhLWcg3w7CfL - Arrow

@MattC，你需要一个常量还是尽可能紧密的常量？如果你只需要任何一个，那么amit的答案对你来说是完美的。如果你需要得到最紧密的可能性，你将需要我上面提到的内容。 - Ivaylo Strandjev

Amit的答案对我来说应该还可以。我不需要太紧凑的内容。但是，我对完全理解它有一点困难... - Arrow

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- amit · Accepted Answer

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

(*) 的原因是对于足够大的 n 值（n>N，其中 N 是某个常数），n/2log(2) < n/4log(n)，因此我们减小“更大”的元素 - 这导致结果较低。

因此，我们得到了 log(n!) >= 1/4*nlog(n)，这使我们可以通过定义使用 c=1/4 得出其属于 Omega(nlogn)。

关于第一部分，我们如何得到 log(n/2) + log(n/2+1) +...+log(n)：

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