作者mirror520 (Mirror Lin)
看板Grad-ProbAsk
标题Re: [问题] 资结-时间复杂度
时间Mon Jun 8 04:18:25 2009
※ 引述《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