※ 引述《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