[理工] 演算法 遞迴

[hl654ck6 (遊戲橘子)]

https://i.imgur.com/qQPa0IQ.jpg
https://i.imgur.com/YPomtTX.jpg
請問compute是怎麼收斂
不太懂這程式怎麼跑的@@求解

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 110.26.32.113
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1539707549.A.6D1.html
推 skyHuan: 如果n<=1就執行atom，否則依題目給的表算X, Y, Z
→ skyHuan: 算出XYZ後跑兩個迴圈
→ skyHuan: 1. s=s+compute
→ skyHuan: 這部分每步的複雜度要看compute函式，總共做了X次你可以
→ skyHuan: 代代看，前三小題看起來可以變成T(n)=X*T(n/Y)+O(1)的形
→ skyHuan: 式，可以用master Thm
→ skyHuan: 2. s=s+atom
→ skyHuan: 這裡atom題目跟你說是O(1)，所以迴圈做Z次就是O(Z)
→ skyHuan: 複雜度就是兩個迴圈加起來，收斂的部分應該就是atom了把
→ skyHuan: 他當O(1)
→ hl654ck6: 我懂了 謝謝