[理工] 算法递回 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

[理工] 算法 递回

[理工] 算法递回