[理工] 时间复杂度 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