作者svanavs (svanavs)
看板Grad-ProbAsk
标题Re: [理工] [资结]-时间复杂度
时间Wed Jul 22 22:33:02 2009
※ 引述《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 => log
n
nlogn => log(
nlogn)
比较
n 与
nlogn :
明显 n = O(nlogn )
所以 logn = O(log(nlogn))
当然 n^log3 = O(nlogn)
--
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 60.198.131.51
1F：推 elfkiller:基本上没错 但没有bounded 07/22 22:52
2F：推 FRAXIS:if f(n) = O(g(n)), then c^f(n) = c^O(g(n)) != O(c^g(n)) 07/22 23:31
3F：→ svanavs:可以给个 c^f(n) = c^O(g(n)) != O(c^g(n)) 的例子吗 ? 07/23 00:27