台大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)