[問題] 兩題複雜度求解
看板Prob_Solve (計算數學 Problem Solving)作者FRAXIS (喔喔)時間14年前 (2010/06/02 22:39)推噓3(3推 0噓 3→)留言6則, 4人參與討論串1/3 (看更多)
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
推
06/02 23:12, , 1F
06/02 23:12, 1F
推
06/03 03:28, , 2F
06/03 03:28, 2F
→
06/03 07:47, , 3F
06/03 07:47, 3F
→
06/03 07:47, , 4F
06/03 07:47, 4F
推
06/10 16:04, , 5F
06/10 16:04, 5F
→
06/10 16:06, , 6F
06/10 16:06, 6F
討論串 (同標題文章)
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
-1
12