作者SmallFoxChiC (小狐狸)
看板Grad-ProbAsk
标题[理工] 资结-时间复杂度
时间Tue Jul 21 20:59:32 2009
请问
log3
n 跟 nlogn 的复杂度是谁比较大呢
可以敎我怎麽看的吗
谢谢大家~
感激不尽~~~~~
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 58.114.98.32
1F：推 nowar100:取log log3logn vs lognlogn 後者大得多 07/21 21:22
2F：→ SmallFoxChiC:我是酱看的 log是取2为底 07/21 22:03
3F：→ SmallFoxChiC:所以取log後 1.xxxlogn 跟 log(nlogn) 07/21 22:04
4F：→ SmallFoxChiC:logn +0.xxxlogn 和 logn + log(logn) 比 07/21 22:04
5F：→ SmallFoxChiC:所以就是0.xxxlogn 和 log(logn) 比 07/21 22:06
6F：→ SmallFoxChiC:然後我觉得是前者比较大XD 07/21 22:07
7F：推 elfkiller:same as O(logn) 07/21 22:12
8F：→ nowar100:我刚也有想把第一项改成3^logn 这样应该是前者较大 07/21 22:16
9F：→ nowar100:今天第一天开始复习 还是不太会看 XD 07/21 22:17
10F：→ SmallFoxChiC:洪捷书上两题都是写说前者较大但没写说为什麽 07/21 23:12
11F：推 nowar100:我发现一楼推文没注意到括号，怪不得後面的会变大得多 07/21 23:39
12F：→ nowar100:这题不用取log 直接把前面的换成 3^logn 这样的话 07/21 23:40
13F：→ nowar100:前面是指数 後面是多项式 所以前面大 流程应该是这样 07/21 23:41
14F：→ doom8199:楼上这样判断会有问题，若题目改成 n^(log2)，若转成 07/22 00:21
15F：→ doom8199:2^(logn)，会以为是指数取向，但实际上那个等於 n 07/22 00:22