[理工] Master Theorem 105 交大

[stayhungry (跳跳跳跳虎)]

請問一下(a)小題
http://i.imgur.com/woHZOlJ.jpg
我的算法為什麼不對？
http://i.imgur.com/r1qdMER.jpg


-----
Sent from JPTT on my Asus ASUS_Z01KDA.

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 180.204.104.55
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1511073463.A.12C.html
→ TMDTMD2487: 怎麼這麼多人相信解答呢XD
→ TMDTMD2487: 還有其實因為3^2=9>8 所以log8(3)一定大於0.5這樣看
→ TMDTMD2487: 比較快一點
→ TMDTMD2487: 總之解答錯的
→ stayhungry: 謝謝 再請問一下這題(E)要怎麼算 答案是Θ(n2 logn) h
→ stayhungry: tp://i.imgur.com/KsPx02s.jpg
→ stayhungry: http://i.imgur.com/K2sEkmy.jpg
→ stayhungry: 用替代法好像也算不出來
※ 編輯: stayhungry (180.204.104.55), 11/19/2017 15:03:17
→ TMDTMD2487: 我映像中這題因為是單選a太好選了我剛做的時候沒算
→ TMDTMD2487: 我後來是用substitution證的
推 TMDTMD2487: https://i.imgur.com/GRemjJk.jpg
→ TMDTMD2487: 恩用這個方法正這個瞬間變得很簡單呢XD
→ stayhungry: http://i.imgur.com/BeZ4WGy.jpg
→ stayhungry: 這題答案又錯了嗎…
→ TMDTMD2487: 哀幹我證錯了我看一下有沒有算太快
→ TMDTMD2487: 我是問句我看看我有沒有算錯
推 gary70812: t大的是否要證出t(k)≦c2*k*logk才算對呢
→ stayhungry: http://i.imgur.com/pT1z4qd.jpg
→ stayhungry: 這是我剛證出來的 也跟答案不一樣@@
推 TMDTMD2487: 對耶很少用這個方法忘記了前面那個C不能亂動XD
→ TMDTMD2487: s大妳乘不能拆開阿sigma不是這樣算的阿XD
→ stayhungry: 所以只要再多乘一個n嗎？不太懂
→ TMDTMD2487: 你倒數第二個等號根本不相等阿OAO
→ TMDTMD2487: (1+...+i)(log1+...+logn)一定大於1log1+...+nlogn
→ stayhungry: http://i.imgur.com/k4Ma8wl.jpg
→ stayhungry:  詳解給的提示是用夾擠法算log i前面多那一項i我就不
→ stayhungry: 會算了@@
推 gary70812: https://i.imgur.com/Qy8t45z.jpg
→ gary70812: 這樣口以嗎
→ stayhungry: 感謝Orz 看的懂了
→ TMDTMD2487: 推導有錯歐
→ TMDTMD2487: https://i.imgur.com/M8xkZG8.jpg
→ TMDTMD2487: 應該可以從這裡推一推找到兩個常數關在n^2logn裡面
→ TMDTMD2487: 不過我不是從這邊推的
→ stayhungry: 嗯嗯 T大寫的對
→ TMDTMD2487: https://i.imgur.com/De2qzB6.jpg
推 gary70812: 對啦寫錯了感謝
→ stayhungry: 謝謝大家提供多種解法Orz
→ stayhungry: T大的解法取上高斯或下高斯有差嗎？
→ TMDTMD2487: 取上介是因為拿掉後大於等於會成立(下介不會成立
→ TMDTMD2487: 如果這邊不等式是要算小於等於就會取下介
→ TMDTMD2487: 這邊這樣取比較嚴謹，當然老師應該是不會看這麼細
→ TMDTMD2487: 不過用定義推倒要嚴謹一點，像最後-1一定要弄成lgn
→ TMDTMD2487: 讓他變成跟你要證的一模一樣的式子然後取一個適當的n0
→ stayhungry: 感謝 有看懂了!