作者FRAXIS (喔喔)
看板Prob_Solve
标题[问题] 两题复杂度求解
时间Wed Jun 2 22:39:08 2010
T(n) = n^0.5 T(n^0.5) + n^0.5
假设n = 2^2^k
T(n) = n^0.5 * (n^0.25 T(n^0.25) + n^0.25) + n^0.5
= n^(1-2^-k) T(0) + n^0.5 + n^0.75 + ....
这边我解不出closed form
T(n) = T(n/2) + T(n^0.5) + n
这题我也用了递回树去展开，也是没办法解出closed form
有人有办法吗？
第一题是93交大资工的考题
第二题是93交大生资的考题
既然是考题应该会有简单的答案吧？
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 140.119.162.50
1F：推 cookiesgreat:第一题用代入法就可以了吧?? 06/02 23:12
3F：→ FRAXIS:我已经代入了.. 只是後面的加总算不出来.. 是我算错了吗？ 06/03 07:47
4F：→ FRAXIS:另外 这两题应该都没办法用master theorem.. 06/03 07:47
5F：推 shaopin:第一题用m=lg(n) changing variable方式再用rec. tree解 06/10 16:04
6F：→ shaopin:第二题也是用m=lg(n)方式...参考自CLRS p66 changing var. 06/10 16:06