[問題] 兩題複雜度求解

看板Prob_Solve作者 (喔喔)時間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
另外 這兩題應該都沒辦法用master theorem..
06/03 07:47, 4F
推
06/10 16:04, , 5F
第一題用m=lg(n) changing variable方式再用rec. tree解
06/10 16:04, 5F
→
06/10 16:06, , 6F
第二題也是用m=lg(n)方式...參考自CLRS p66 changing var.
06/10 16:06, 6F
‣ 更多 FRAXIS 的文章
文章代碼(AID): #1C1cqFei (Prob_Solve)
‣ 更多 FRAXIS 的文章
文章代碼(AID): #1C1cqFei (Prob_Solve)