作者nowar100 (抛砖引玉)
看板Grad-ProbAsk
标题Re: [理工] [资结]-时间复杂度
时间Wed Jul 22 09:26:58 2009
※ 引述《SmallFoxChiC (小狐狸)》之铭言：
log3
n 跟 nlogn 的复杂度是谁比较大呢
1F：→ SmallFoxChiC:洪捷书上两题都是写说前者较大但没写说为什麽 07/21 23:12
2F：推 nowar100:我发现一楼推文没注意到括号，怪不得後面的会变大得多 07/21 23:39
3F：→ nowar100:这题不用取log 直接把前面的换成 3^logn 这样的话 07/21 23:40
4F：→ nowar100:前面是指数 後面是多项式 所以前面大 流程应该是这样 07/21 23:41
5F：→ doom8199:楼上这样判断会有问题，若题目改成 n^(log2)，若转成 07/22 00:21
6F：→ doom8199:2^(logn)，会以为是指数取向，但实际上那个等於 n 07/22 00:22
这样呢？
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 )
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 140.113.93.39
7F：推 FRAXIS:上下先同除n 再用罗必达会比较方便些 07/22 23:33
8F：→ nowar100:谢谢 没想到 07/23 00:19