[理工] 演算法複雜度 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大

繼續閱讀