[理工] 演算法 master theory newpuma PTT批踢踢實業坊

[理工] 演算法 master theory

作者: newpuma (還很新) 2016-11-26 19:29:18

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）

作者: kyuudonut (å–„è‰¯è€ç™¾å§“) 2016-11-29 01:24:00

關鍵字: p-series, harmonic number power > 2 會收斂

作者: k2shouai (coding....) 2016-11-26 19:54:00

這種master theory就是不能用

作者: hopward (hopward) 2016-11-26 20:00:00

只能爆開了

作者: darren0831 (達) 2016-11-26 20:04:00

這種log放分母的的確有公式但我沒記XD

作者: ken52011219 (呱) 2016-11-26 21:02:00

少一個條件,否則算得出來我先PO原解答,但我看不懂Qhttp://imgur.com/a/TXnQj http://i.imgur.com/73eFQDs.jpg 這是我算的重PO http://imgur.com/a/Wh5KB

作者: PTTleader (PTT領導) 2016-11-26 21:23:00

lgn在分母>=2次就直接省略

作者: leoone (里歐一代) 2016-11-26 22:24:00

log 在分母算出來的K會小於0 不能用M theory

作者: FRAXIS (喔喔) 2016-11-26 23:27:00

要公式就只能用 Akra–Bazzi method 了

作者: ken52011219 (呱) 2016-11-27 06:46:00

推樓上 F大整理的資料受用無窮但可以講解一下為什麼可以變 n/(lg (n-1))^2嗎

作者: FRAXIS (喔喔) 2016-11-27 13:18:00

我打錯了應該是 n/ ((lg n) - 1)^2

作者: ken52011219 (呱) 2016-11-27 13:20:00

了解感謝！回家再研究看看

作者: FRAXIS (喔喔) 2016-11-27 13:26:00

其實就只是把 T(n/2) 再用遞迴式展開而已..

繼續閱讀

[理工] 演算法maximum matchinghopward [理工] [線代]104台大資工ex8338 [理工]線代列獨立 LKer kerab830921 [理工] [流體力學] 平板間層流prospectof [理工] 線代-內積問題pureblue1234 [理工] OS two level pagegary19941208 [理工][演算法]fraction knapsack 時間h9638512 [理工][資結] binary treeh9638512 [理工] 91台大機械問題jim510032000 Re: [理工] 離散 2^N (power set of N)為不可數集kyuudonut