Re: [理工] [資結]-時間複雜度
※ 引述《nowar100 (拋磚引玉)》之銘言：
: ※ 引述《SmallFoxChiC (小狐狸)》之銘言：
: log3
: n 跟 nlogn 的複雜度是誰比較大呢
: lg3 lg3-1 lg3-2
: n lg3 n lg3 (lg3-1) n
: lim -------- = lim ----------- = lim -------------------
: n->∞ nlgn lgn + 1 1 / n
: lg3-1
: = lg3 (lg3-1) lim n = ∞
: lg3
: ∴ nlgn = O (n )
這是在你底是2的情況 也就是說 lg3-1是大於0沒錯
但是 log3-1 = 0.47712... -1 = -0.622... 是 < 0
log3-1
所以 log3 (log3-1) lim n = 0
n^log3 = O(nlogn)
======================================================
我的解法是各自取log :
n^log3 => (log3)(logn) = 常數*logn => logn
nlogn => log(nlogn)
比較 n 與 nlogn :
明顯 n = O(nlogn )
所以 logn = O(log(nlogn))
當然 n^log3 = O(nlogn)
--
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 60.198.131.51
推
07/22 22:52, , 1F
07/22 22:52, 1F
推
07/22 23:31, , 2F
07/22 23:31, 2F
→
07/23 00:27, , 3F
07/23 00:27, 3F
討論串 (同標題文章)