Re: [理工] [演算法] 遞迴式問題

看板Grad-ProbAsk作者 (喔喔)時間15年前 (2010/06/15 12:22), 編輯推噓3(3推 0噓 9→)
留言12則, 2人參與, 最新討論串1/3 (看更多)
※ 引述《mqazz1 (無法顯示)》之銘言： : Use the idea of subtleties to solve the following recurrence: : T(n) = T(n/3) + T(2n/3) + n^(1/2) 可以用疊代一直展開，到最後會變成 O(n) + n^(1/2) + (n/3)^0.5 + (2n/3)^0.5 + .... 應該就變成O(n)吧.. : Use the idea of changing variable to solve the following recurrence: : T(n) = T(n^1/2) + 1 令 n = 2^2^k, F(k) = T(2^2^k) F(k) = F(k-1) + 1 解開F(k) = O(k) 所以T(n) = O(lglg n) -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.119.162.50
推
06/15 14:35, , 1F
第一題的答案應該是n^(1/2)log(n):x
06/15 14:35, 1F
→
06/15 14:36, , 2F
後面:x是多的= =
06/15 14:36, 2F
→
06/15 17:16, , 3F
那個答案不太可能.. 因為光是遞迴樹展開到底就有O(n)個
06/15 17:16, 3F
→
06/15 17:17, , 4F
leaves了，比O(n)還小的答案很奇怪 除非我理解錯誤..
06/15 17:17, 4F
推
06/15 17:52, , 5F
請把課本看熟 遞回樹每一階的成本加起來剛好是n
06/15 17:52, 5F
→
06/15 17:53, , 6F
所以是那個答案
06/15 17:53, 6F
推
06/15 17:56, , 7F
不知道你有沒有"演算法-名校功略秘笈"這一本書
06/15 17:56, 7F
→
06/15 17:57, , 8F
裡面第2-20頁範例5中的第5題跟此題目一模一樣
06/15 17:57, 8F
→
06/15 17:58, , 9F
裡面有詳解
06/15 17:58, 9F
→
06/15 17:58, , 10F
nlogn
06/15 17:58, 10F
→
06/15 17:59, , 11F
ㄆㄆ
06/15 17:59, 11F
→
06/15 18:00, , 12F
每一階成本乘上樹高= =
06/15 18:00, 12F
‣ 更多 FRAXIS 的文章
文章代碼(AID): #1C5m0AqT (Grad-ProbAsk)
‣ 更多 FRAXIS 的文章
文章代碼(AID): #1C5m0AqT (Grad-ProbAsk)