推 elfkiller:基本上沒錯 但沒有bounded 07/22 22:52
推 FRAXIS:if f(n) = O(g(n)), then c^f(n) = c^O(g(n)) != O(c^g(n)) 07/22 23:31
→ svanavs:可以給個 c^f(n) = c^O(g(n)) != O(c^g(n)) 的例子嗎 ? 07/23 00:27
※ 引述《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