→ SmallFoxChiC:洪捷書上兩題都是寫說前者較大但沒寫說為什麼 07/21 23:12
推 nowar100:我發現一樓推文沒注意到括號，怪不得後面的會變大得多 07/21 23:39
→ nowar100:這題不用取log 直接把前面的換成 3^logn 這樣的話 07/21 23:40
→ nowar100:前面是指數 後面是多項式 所以前面大 流程應該是這樣 07/21 23:41
→ doom8199:樓上這樣判斷會有問題，若題目改成 n^(log2)，若轉成 07/22 00:21
→ 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
推 FRAXIS:上下先同除n 再用羅必達會比較方便些 07/22 23:33
→ nowar100:謝謝 沒想到 07/23 00:19