[理工] 時間複雜度 ss455032 PTT批踢踢實業坊

[理工] 時間複雜度

作者: ss455032 (ss455032) 2017-10-17 10:54:16

想請問一下為什麼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
謝謝

作者: brilliantl (brilliant) 2017-10-17 11:08:00

T(i,j)可以想成for loop做j-i次，所以j-i的值相同，T(i,j)也相同+c應該是for之前的cost吧

作者: q1qip123 (wtlee) 2017-10-17 11:36:00

但是for裡面也有計算，所以那個c也有包括吧？另外這個好像dp問題這樣叫combine cost好像也不太適合？

作者: shownlin (哈哈阿喔) 2017-10-25 01:04:00

除了recursion的時間，其他的運算都跟input size無關取常數就好

繼續閱讀

Re: [理工] 離散排列組合JKLee [理工] 計組上冊 P533 #12w0960346 [理工] 解未知數的運算疑問linbada [理工] 演算法minimum edit distancez0953781935 ［演算法］ 0／1 knapsack problemq1qip123 [理工] 離散排列組合tte09567 [理工] 資結 permutation的時間複雜度q5332159 [理工] 資結 2-3-4Tree 99暨南ahahahahah [理工] 計組上冊 P.234ddd23236 [徵求]徵聖經本:資料結構,作業系統,計組,演算法a5204860