作者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