[問題] 兩題複雜度求解

[FRAXIS (喔喔)]

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
推 cookiesgreat:第一題用代入法就可以了吧??
推 flamerecca:http://en.wikipedia.org/wiki/Master_theorem 這個？
→ FRAXIS:我已經代入了.. 只是後面的加總算不出來.. 是我算錯了嗎？
→ FRAXIS:另外 這兩題應該都沒辦法用master theorem..
推 shaopin:第一題用m=lg(n) changing variable方式再用rec. tree解
→ shaopin:第二題也是用m=lg(n)方式...參考自CLRS p66 changing var.