[理工] 時間複雜度

[ss455032 (ss455032)]

想請問一下為什麼T(2,n)+...+T(n,n)會跟T(1,2)+...+T(1,n-1)一樣呢.
另外想問為什麼只有+c是因為p[i-1,k,j]這矩陣的combine cost?
https://i.imgur.com/W2zbGot.jpg
https://i.imgur.com/68y3zOF.jpg
謝謝

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 42.73.204.138
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1508208858.A.E06.html
推 brilliantl: T(i,j)可以想成for loop做j-i次，所以j-i的值相同，T(
→ brilliantl: i,j)也相同
→ brilliantl: +c應該是for之前的cost吧
推 q1qip123: 但是for裡面也有計算，所以那個c也有包括吧？
→ q1qip123: 另外這個好像dp問題 這樣叫combine cost好像也不太適合
→ q1qip123: ？
推 shownlin: 除了recursion的時間，其他的運算都跟input size無關
→ shownlin:  取常數就好