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

看板Grad-ProbAsk作者 (小澤)時間16年前 (2010/02/17 11:36), 編輯推噓5(5推 0噓 14→)
留言19則, 6人參與, 最新討論串1/1
想問幾個比大小 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
→
02/17 11:41, , 1F
n^n >n!=2^(lgn!)=2^(nlgn)=(2^n)^lgn>n^lgn
02/17 11:41, 1F
→
02/17 11:42, , 2F
n^lglgn=(lgn)^lgn>lgn!
02/17 11:42, 2F
n! = 2^(lgn!) ?= 2^(nlgn) 2^(nlgn) = 2^(lgn^n) = (n^n)^lg2 = n^n ? ※ 編輯: polomoss 來自: 122.116.14.2 (02/17 11:51)
→
02/17 11:49, , 3F
n^2=2^(2lgn)>2^sqrt(2lgn)=n^sqrt(2/lgn)
02/17 11:49, 3F
→
02/17 11:52, , 4F
跟n^1比呢?
02/17 11:52, 4F
推
02/17 12:03, , 5F
n^1>2^sqrt(2lgn)
02/17 12:03, 5F
推
02/17 12:07, , 6F
n^1=2^(lgn)>2^sqrt(2lgn) 我是這樣想的 討論看看摟
02/17 12:07, 6F
→
02/17 12:21, , 7F
我發現 2^sqrt(2lgn) 比 n^1/2還要小
02/17 12:21, 7F
→
02/17 12:35, , 8F
矛盾了QQ 可是我直覺上 n!比n^lgn大啦 因為n!趨近n^n
02/17 12:35, 8F
推
02/17 13:21, , 9F
n! > n^lgn 用Strling's Approximation就可以看出來了.
02/17 13:21, 9F
推
02/17 14:03, , 10F
怎嚜看阿@@ n!約 n^(n+1/2)*e^(-n) 和 n^lgn 比較
02/17 14:03, 10F
→
02/17 14:22, , 12F
看起來的確是耶, 有個sqrt(n)*n^n
02/17 14:22, 12F
→
02/18 01:34, , 13F
弄成stirling approximation 之後 要怎樣比阿 ? 取log ?
02/18 01:34, 13F
→
02/18 10:53, , 14F
你可以微分lgn + 1次..
02/18 10:53, 14F
→
02/18 11:00, , 15F
喔喔... 感謝回答!
02/18 11:00, 15F
→
02/18 11:22, , 16F
不過直接對 n! 和 n^lgn 取 log 比較會不會比較快阿 ?
02/18 11:22, 16F
→
02/18 11:22, , 17F
一個會接近於 nlgn 一個變成 lglgn 所以前者較大 @@ ?
02/18 11:22, 17F
推
02/18 11:29, , 18F
也可以 不過n^lgn取lg是(lgn)^2
02/18 11:29, 18F
→
02/18 11:31, , 19F
喔對 打錯了 XD
02/18 11:31, 19F
‣ 更多 polomoss 的文章
文章代碼(AID): #1BUsGZei (Grad-ProbAsk)