※ 引述《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