[理工] 演算法遞迴 hl654ck6 PTT批踢踢實業坊

[理工] 演算法遞迴

作者: hl654ck6 (遊戲橘子) 2018-10-17 00:32:26

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

作者: skyHuan (Huan) 2018-10-17 10:59:00

如果n<=1就執行atom，否則依題目給的表算X, Y, Z算出XYZ後跑兩個迴圈1. s=s+compute這部分每步的複雜度要看compute函式，總共做了X次你可以代代看，前三小題看起來可以變成T(n)=X*T(n/Y)+O(1)的形式，可以用master Thm2. s=s+atom這裡atom題目跟你說是O(1)，所以迴圈做Z次就是O(Z)複雜度就是兩個迴圈加起來，收斂的部分應該就是atom了把他當O(1)

作者: hl654ck6 (遊戲橘子) 2018-10-17 13:12:00

我懂了謝謝

繼續閱讀

[理工] 演算法MST第35題wilson50101 [理工] 離散 9.6 陪集 - 循環群證明befdawn [理工] Memory Dora5566 請求交大吳炳飛老師的線性系統講義layre0905tw Re: [理工] 離散有限狀態機skyHuan [理工] 離散有限狀態機AAQ8 [理工] 離散圖論TEPLUN [理工] 張凡下冊140tataTangQQ Fw: [問題] CMOS輸出入電阻suspect1 [理工] 計組下冊 P.351 Omega networkjojoboy0115

[理工] 演算法 遞迴

[理工] 演算法遞迴