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

[FRAXIS (喔喔)]

※ 引述《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
推 kill2400:第一題的答案應該是n^(1/2)log(n):x
→ kill2400:後面:x是多的= =
→ FRAXIS:那個答案不太可能.. 因為光是遞迴樹展開到底就有O(n)個
→ FRAXIS:leaves了，比O(n)還小的答案很奇怪 除非我理解錯誤..
推 kill2400:請把課本看熟 遞回樹每一階的成本加起來剛好是n
→ kill2400:所以是那個答案
推 kill2400:不知道你有沒有"演算法-名校功略秘笈"這一本書
→ kill2400:裡面第2-20頁範例5中的第5題跟此題目一模一樣
→ kill2400:裡面有詳解
→ kill2400:nlogn
→ kill2400:ㄆㄆ
→ kill2400:每一階成本乘上樹高= =