作者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/cn.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