[理工] [資結]-複雜度比大小

[polomoss (小澤)]

想問幾個比大小


n! ,n^lgn, n^n


(logn)!, n^lglgn



還有 2^sqrt(2lgn) = n ^ sqrt(2/lgn) 這個數介於哪阿?

跟 n^1  n^k 比呢



謝謝

--
     ◤    ◥  答      ◤    ◥  拉      ◤    ◥  米      ◤    ◥  哆
   Σ ◆  ◆   蚊    Σ ◆  ◆   肥    Σ ◆  ◆   開    Σ ◆  ◆   啦
        ︵     吸         ︵     兒         ︵     喇         ︵     太
    ◣++++++◢        ◣++++++◢        ◣++++++◢ 雞     ◣++++++◢ 裸
◥▇▆@ ≡ @▆▇◤     Ψ ≡ Ψ          ▄ ≡ ▄  囉  ▄▄▄ ≡ ▄▄▄
        ▅                ▅          ▄/   ▅   \▄          ▅  ＡΓＶＩＳＳ

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 122.116.14.2
→ taitin:n^n >n!=2^(lgn!)=2^(nlgn)=(2^n)^lgn>n^lgn
→ taitin:n^lglgn=(lgn)^lgn>lgn!
n! = 2^(lgn!) ?= 2^(nlgn)

2^(nlgn) = 2^(lgn^n) = (n^n)^lg2 = n^n ?
※ 編輯: polomoss        來自: 122.116.14.2         (02/17 11:51)
→ taitin:n^2=2^(2lgn)>2^sqrt(2lgn)=n^sqrt(2/lgn)
→ polomoss:跟n^1比呢?
推 shengwen323:n^1>2^sqrt(2lgn)
推 shengwen323:n^1=2^(lgn)>2^sqrt(2lgn)  我是這樣想的 討論看看摟
→ polomoss:我發現 2^sqrt(2lgn) 比 n^1/2還要小
→ taitin:矛盾了QQ 可是我直覺上 n!比n^lgn大啦 因為n!趨近n^n
推 FRAXIS:n! > n^lgn 用Strling's Approximation就可以看出來了.
推 EntHeEnd:怎嚜看阿@@ n!約 n^(n+1/2)*e^(-n) 和 n^lgn 比較
→ BenLinus:http://en.wikipedia.org/wiki/Stirling's_approximation
→ BenLinus:看起來的確是耶, 有個sqrt(n)*n^n
→ EntHeEnd:弄成stirling approximation 之後 要怎樣比阿 ? 取log ?
→ FRAXIS:你可以微分lgn + 1次..
→ EntHeEnd:喔喔... 感謝回答!
→ EntHeEnd:不過直接對 n! 和 n^lgn 取 log 比較會不會比較快阿 ?
→ EntHeEnd:一個會接近於 nlgn 一個變成 lglgn 所以前者較大 @@ ?
推 FRAXIS:也可以 不過n^lgn取lg是(lgn)^2
→ EntHeEnd:喔對 打錯了 XD