台大103的第1题的第2小题
T(n) = T(n/2 + √n) + n
这题我真的没有想法,用recursion-tree弄出一大推奇奇怪怪的东西
成大102的计算题的第1小题
T(n) = 2T(n/2) + n/lgn
这题我看T○B的名校攻略上写是O(nlglgn)
想请问是怎么来的我已经知道每层是n/(-i+lgn)了
要怎么把n/(-i+lgn)化成O(nlglgn)啊
还有成大103第2题想跟大家对下
我写:若M极大:T(n)=M :O(1)
M极小:T(n)=16T(n/2)+Θ(1) :O(n^4)
可是感觉有点怪怪的,想参考神人们的写法看看

2. recur tree 弄出来是 n(1/1+1/2+...+1/lgn)=nlglgn最后我觉得是O(n^4)..

成大那题用extended master method就可以解决了，如果我没弄错的话补充一下是成大102第一小题

不能用吧@@ 他不符合条件

成大102那题就令n=2^k，然后用叠代

噢我看错了不要理我哈

超感谢hbkhhhdx2006大提供一个超棒的想法啊有人有台大那题的想法吗?

用substitution method去证T(n)=O(n)