※ 引述《nowar100 (拋磚引玉)》之銘言：
: ※ 引述《SmallFoxChiC (小狐狸)》之銘言：
: log3
: n 跟 nlogn 的複雜度是誰比較大呢
: → 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 )
n大太認真了.....佩服
我也是跟n大想法一樣
log3 logn
n 換底後 3
logn
3 > nlogn
d大說如果他題目改成
log2
n --->基本上因該不會有人在去換底 直接反應因該就是 n
除非他的基底有另外定 不過這提爭議有點大的話 出題大部分會避免掉才對
PS:以上個人想法僅可參考
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 218.168.193.49