證明log（n！）是Ω（n log（n））

Question

我們的操作總成本是：Σ（i = 1到n）log（i）。

證明這個和是Ω（n log（n））。

我有點卡在如何去證明這一點。由於log（1）+ log（2）+ log（3）= log（3！）（等等等等），我知道總結出來是log（n！）

但是然後我'米卡在哪裏去正式證明。任何幫助，將不勝感激！

Answer 1

你確定，它是大的歐米茄而不是大的O，因爲我認爲每個日誌（i），0 < = n，可以表示爲O（log（n）），所以求和會給你O（nlog（n））

Answer 2

你最簡單的攻擊是爭辯\ sum {i = 1}^{n} \ log（i）< \ sum {i = 1}^{n} \ log （n），然後顯示你的加數與指數無關。或者，你可以顯示n！ < n^n，然後應用日誌的屬性來得到您的答案。