TA貢獻(xiàn)1880條經(jīng)驗(yàn) 獲得超4個(gè)贊
記住
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)
在丟棄總和的前一半之后，您可以通過執(zhí)行類似的操作來獲得下界：
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)
TA貢獻(xiàn)1839條經(jīng)驗(yàn) 獲得超15個(gè)贊
我意識(shí)到這是一個(gè)非常老的問題，答案是可以接受的，但是這些答案實(shí)際上都沒有使用提示所建議的方法。
這是一個(gè)非常簡(jiǎn)單的參數(shù)：
n!（= 1 * 2 * 3 * ... * n）是n每個(gè)均小于或等于的數(shù)字的乘積n。因此它小于n全部等于的數(shù)字的乘積n; 即n^n。
產(chǎn)品中一半的數(shù)字（即n/2其中的數(shù)字）n!大于或等于n/2。因此他們的乘積大于n/2全部等于的數(shù)字的乘積n/2; 即(n/2)^(n/2)。
全面記錄日志以確定結(jié)果。
TA貢獻(xiàn)1906條經(jīng)驗(yàn) 獲得超3個(gè)贊
對(duì)于下限，
lg(n!) = lg(n)+lg(n-1)+...+lg(n/2)+...+lg2+lg1
>= lg(n/2)+lg(n/2)+...+lg(n/2)+ ((n-1)/2) lg 2 (leave last term lg1(=0); replace first n/2 terms as lg(n/2); replace last (n-1)/2 terms as lg2 which will make cancellation easier later)
= n/2 lg(n/2) + (n/2) lg 2 - 1/2 lg 2
= n/2 lg n - (n/2)(lg 2) + n/2 - 1/2
= n/2 lg n - 1/2
lg（n！）> =（1/2）（n lg n-1）
結(jié)合兩個(gè)界限：
1/2（n lg n-1）<= lg（n?。?lt;= n lg n
通過選擇大于（1/2）的下界常數(shù)，我們可以補(bǔ)償括號(hào)內(nèi)的-1。
因此lg（n！）= Theta（n lg n）
舉報(bào)