Re: [問題] 資結-時間複雜度
※ 引述《shinhwabo (.....)》之銘言：
: Ordering by asymptotic growth rates
: (a)lg(n!) (b)4^lgn (c)(n-1)! (d)n‧2^n (e)(lgn)^lgn
: 實在不知道怎麼判斷!?
: 有高手可以解答嗎@@
(a) log(n!) = O(nlogn)
Stirling 公式: n!≒n^(n+1/2)*e^(-n)
∴log(n!) ≒ log((n^n+1/2)*e^(-n)) = log(n^n+1/2) + log(e^-n)
= (n+1/2) * logn - n
= nlogn + (1/2)logn - n
∴ Time is O(nlogn)
(b) 4^logn = O(n^2) 平方
4^logn = n^log4 = n^2
∴Time is O(n^2)
(c) (n-1)! = O(n!) 階層
(d) n*2^n = O(n*2^n) 指數
(e) logn^logn = O(n^loglogn) 指數
等級: 階層 > 指數 > 平方 > 線行 > 對數 > 常數
c > d > e > b > a
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 114.41.137.44
討論串 (同標題文章)