[理工] 演算法 master theory

[newpuma (還很新)]

http://i.imgur.com/Utarcds.jpg

master theory好像沒有讀到這種case

看到額外補充只有

T(n)=2T(n/2)+nlgn
T(n)是nlg^2n
跟
T(n)=2T(n/2)+n/lgn
T(n)是nlglgn

好像沒有lg的指數是負數的其他case？這題在master theory中有什麼更好的判定方式嗎
？還是lg的負數指數太高就直接忽略？（此題答案是n^2）

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 223.137.3.213
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1480159760.A.CCF.html
推 k2shouai: 這種master theory就是不能用
→ hopward: 只能爆開了
推 darren0831: 這種log放分母的的確有公式但我沒記XD
有公式 嗎？
我的筆記只有lg放分母但一次方的
※ 編輯: newpuma (223.137.3.213), 11/26/2016 20:17:12
→ ken52011219: 少一個條件,否則算得出來 我先PO原解答,但我看不懂Q
→ ken52011219: http://imgur.com/a/TXnQj
→ ken52011219:  http://i.imgur.com/73eFQDs.jpg 這是我算的
→ ken52011219: 重PO http://imgur.com/a/Wh5KB
推 PTTleader: lgn在 分母>=2次 就直接省略
推 leoone: log 在分母 算出來的K會小於0 不能用M theory
推 FRAXIS: 要公式就只能用 Akra–Bazzi method 了
推 ken52011219: 推樓上 F大整理的資料受用無窮 但可以講解一下為什
→ ken52011219: 麼可以變 n/(lg (n-1))^2嗎
推 FRAXIS: 我打錯了 應該是 n/ ((lg n) - 1)^2
推 ken52011219: 了解感謝！回家再研究看看
推 FRAXIS: 其實就只是把 T(n/2) 再用遞迴式展開而已..
推 kyuudonut: 關鍵字: p-series, harmonic number power > 2 會收斂