asymptotic-complexity - 证明 log(n!) 的单位是 Ω(n log(n))

Question

我们操作的总成本是：Σ(i=1 to n) log(i)。

证明这个和是 Ω(n log(n))。

我对如何证明这一点有点困惑。我意识到总和是 log(n!)，因为 log(1) + log(2) + log(3) = log(3!) （等等）

但是后来我被困在去哪里获得正式证明。任何帮助，将不胜感激！

Answer 1

你确定它是大欧米茄而不是大 O，因为我认为每个 log(i) 0 <= i <= n 都可以表示为 O(log(n)) ，所以求和会给你 O(日志（n））

Answer 2

你最简单的攻击是争论 \sum{i=1}^{n}\log(i) < \sum{i=1}^{n}\log(n)，然后表明你的 summand 是独立于索引. 或者，您可以证明 n! < n^n，然后应用日志的属性来得到你的答案。