演算法漸進複雜度，怎麼證明logn!= θ（nlogn）？

01-05

$nln(n) - n + 1 = int_{1}^n ln(x) mathrm{d}x leq sum_{i=2}^n ln(i) = ln(n!) = sum_{i = 1}^n ln(i) leq int_{1}^{n + 1} ln(x) mathrm{d}x = (n + 1)ln(n + 1) - n$

根據斯特林公式 $n!=sqrt{2pi n}ig(frac{n}{e}ig)^n$

閑來無事，隨手放縮一下（對於足夠大的 $n$ ）：

$ecause (n/2)^{n/2} leq n! leq n^n,$

$herefore n/4log(n) = n/2log(n^{1/2}) leq n/2log(n/2) leq log(n!) leq nlog(n)$

雖然17年了，我也回答下吧，是我們演算法課的作業題。

n!=n(n-1)...1

則有n!&<=nn...n=n**n

將n!的前一半拋去，即為n/2 ...n，再均取值為n/2，則n!必定大於n/2個n/2的乘積，則

（n/2）**（n/2）&< n! &< n ** n，兩邊同時取lg即可得證

豪爽地放一下，n階乘小於等於n的n次方，大於等於n的二分之n次方，後面怎麼辦就很明顯了吧。

前面的同學連斯特林和積分都出來了，證明這種東西不用太精確。