推 shinhwabo:感謝^^ 06/09 15:33
※ 引述《nowar100 (拋磚引玉)》之銘言：
: ※ 引述《shinhwabo (.....)》之銘言：
: : Ordering by asymptotic growth rates
: : (a)lg(n!) (b)4^lgn (c)(n-1)! (d)n‧2^n (e)(lgn)^lgn
: (a) = lg(n * n-1 * n-2 * ... * 1)
: = lg(n) + lg(n-1) + ...
: = O (lgn)
......= =
lg(n!)=Θ(nlgn)
pf: (a) = lg(1*2*3*...*n)
= lg1 + lg2 + lg3 + ... +lg n <= nlgn
O(nlgn)
= lg1 + lg2 + lg3 + ... +lg n >= lg(n/2)+lg(n/2+1)+...+lgn
>= lg(n/2)+lg(n/2)...+lg(n/2)
=(n/2)*lg(n/2)
Ω(nlgn)
故(a)=Θ(nlgn)
: (c) = O (n^2)
應該是(b)= Θ(n^2)
4^lgn = n^lg4 = n^2
: b,d,e 各取lg，為b',d',e'
: (b') = lgn * lg4 = O (lgn)
: (d') = lgn + nlg2 = O (n)
: (e') = lgnlgn = O (lgn^2)
: c > a > d > e > b
Θ(n!) < Θ(2^n) 應該沒有問題
最後比較 (lgn)^lgn 和 n!
同取lg，得 lgn*lglgn 和 nlgn (同(a)小題可得)
故 Θ(lgn)^lgn < Θ(n!)
就可以排序了
: 還沒念，憑修課的印像回答
: : 實在不知道怎麼判斷!?
: : 有高手可以解答嗎@@
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 218.174.38.165