[理工] 算法复杂度 104中央 painechaos PTT批踢踢实业坊

楼主: painechaos (老赵) 2017-11-18 18:19:03

想请问下图我打星号的地方，不懂为什么可以直接变成2倍，原本的想法是可能
T(2,n)=T(1,n-1)之类的，但代进计算后又觉得怪怪的
http://i.imgur.com/8ltwL9g.jpg

作者: nat99up (NAt) 2017-11-18 18:49:00

j-i才是input size(1,n-1)跟(2,n)花的时间是一样的

作者: kai3570 (kai3570) 2017-11-18 21:18:00

(1,1) = (n,n) , (1,2) = (n-1,n)以此类推...(1,n-1) = (2,n)所以前后两串时间相等

作者: sarsman (DeNT15T♠) 2017-11-18 23:01:00

耗费时间相等即可合并

楼主: painechaos (老赵) 2017-11-18 23:01:00

谢谢两位大大! 我再研究看看s大也谢谢你

作者: nat99up (NAt) 2017-11-19 14:14:00

不会看程式码就知道iteratibe body是常数时间

楼主: painechaos (老赵) 2017-11-19 20:39:00

好的! 谢谢n大

继续阅读