[理工] 演算法 遞迴

看板Grad-ProbAsk作者 (遊戲橘子)時間7年前 (2018/10/17 00:32), 編輯推噓1(1推 0噓 10→)
留言11則, 2人參與, 7年前最新討論串1/1
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
推
10/17 10:59, 7年前 , 1F
如果n<=1就執行atom，否則依題目給的表算X, Y, Z
10/17 10:59, 1F
→
10/17 11:09, 7年前 , 2F
算出XYZ後跑兩個迴圈
10/17 11:09, 2F
→
10/17 11:09, 7年前 , 3F
1. s=s+compute
10/17 11:09, 3F
→
10/17 11:09, 7年前 , 4F
這部分每步的複雜度要看compute函式，總共做了X次你可以
10/17 11:09, 4F
→
10/17 11:09, 7年前 , 5F
代代看，前三小題看起來可以變成T(n)=X*T(n/Y)+O(1)的形
10/17 11:09, 5F
→
10/17 11:09, 7年前 , 6F
式，可以用master Thm
10/17 11:09, 6F
→
10/17 11:09, 7年前 , 7F
2. s=s+atom
10/17 11:09, 7F
→
10/17 11:09, 7年前 , 8F
這裡atom題目跟你說是O(1)，所以迴圈做Z次就是O(Z)
10/17 11:09, 8F
→
10/17 11:10, 7年前 , 9F
複雜度就是兩個迴圈加起來，收斂的部分應該就是atom了把
10/17 11:10, 9F
→
10/17 11:10, 7年前 , 10F
他當O(1)
10/17 11:10, 10F
→
10/17 13:12, 7年前 , 11F
我懂了 謝謝
10/17 13:12, 11F
‣ 更多 hl654ck6 的文章
文章代碼(AID): #1RnXATRH (Grad-ProbAsk)