[理工] 算法 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