作者hl654ck6 (遊戲橘子)
看板Grad-ProbAsk
標題[理工] 演算法 遞迴
時間Wed Oct 17 00:32:26 2018
https://i.imgur.com/qQPa0IQ.jpg
https://i.imgur.com/YPomtTX.jpg
請問compute是怎麼收斂
不太懂這程式怎麼跑的@@求解
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 110.26.32.113
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Grad-ProbAsk/M.1539707549.A.6D1.html
1F：推 skyHuan: 如果n<=1就執行atom，否則依題目給的表算X, Y, Z 10/17 10:59
2F：→ skyHuan: 算出XYZ後跑兩個迴圈 10/17 11:09
3F：→ skyHuan: 1. s=s+compute 10/17 11:09
4F：→ skyHuan: 這部分每步的複雜度要看compute函式，總共做了X次你可以 10/17 11:09
5F：→ skyHuan: 代代看，前三小題看起來可以變成T(n)=X*T(n/Y)+O(1)的形 10/17 11:09
6F：→ skyHuan: 式，可以用master Thm 10/17 11:09
7F：→ skyHuan: 2. s=s+atom 10/17 11:09
8F：→ skyHuan: 這裡atom題目跟你說是O(1)，所以迴圈做Z次就是O(Z) 10/17 11:09
9F：→ skyHuan: 複雜度就是兩個迴圈加起來，收斂的部分應該就是atom了把 10/17 11:10
10F：→ skyHuan: 他當O(1) 10/17 11:10
11F：→ hl654ck6: 我懂了 謝謝 10/17 13:12