[理工] 演算法 複雜度 104中央

[painechaos (老趙)]

想請問下圖我打星號的地方，不懂為什麼可以直接變成2倍，原本的想法是可能
T(2,n)=T(1,n-1)之類的，但代進計算後又覺得怪怪的

http://i.imgur.com/8ltwL9g.jpg

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.47.192.130
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1511000346.A.67B.html
推 nat99up: j-i才是input size
→ nat99up: (1,n-1)跟(2,n)花的時間是一樣的
→ kai3570: (1,1) = (n,n)  ,  (1,2) = (n-1,n)
→ kai3570: 以此類推...(1,n-1) = (2,n)
→ kai3570: 所以前後兩串時間相等
推 sarsman: 耗費時間相等即可合併
→ painechaos: 謝謝兩位大大! 我再研究看看
→ painechaos: s大也謝謝你
→ painechaos: 昨天思考完還是有點卡住@@
→ painechaos: 想請問是如何知道,若(y-x)=(v-u),則T(x,y)=T(u,v)的，
→ painechaos: 我一直思考會不會跟切鐵棒問題一樣，有不同的權重
→ nat99up: 不會 看程式碼就知道iteratibe body是常數時間
→ painechaos: 好的! 謝謝n大