[理工] 時間複雜度

看板Grad-ProbAsk作者 (ss455032)時間6年前 (2017/10/17 10:54), 編輯推噓3(3推 0噓 5→)
留言8則, 3人參與, 6年前最新討論串8/12 (看更多)
想請問一下為什麼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
推
10/17 11:08, 6年前 , 1F
T(i,j)可以想成for loop做j-i次，所以j-i的值相同，T(
10/17 11:08, 1F
→
10/17 11:08, 6年前 , 2F
i,j)也相同
10/17 11:08, 2F
→
10/17 11:11, 6年前 , 3F
+c應該是for之前的cost吧
10/17 11:11, 3F
推
10/17 11:36, 6年前 , 4F
但是for裡面也有計算，所以那個c也有包括吧？
10/17 11:36, 4F
→
10/17 11:36, 6年前 , 5F
另外這個好像dp問題 這樣叫combine cost好像也不太適合
10/17 11:36, 5F
→
10/17 11:36, 6年前 , 6F
？
10/17 11:36, 6F
推
10/25 01:04, 6年前 , 7F
除了recursion的時間，其他的運算都跟input size無關
10/25 01:04, 7F
→
10/25 01:04, 6年前 , 8F
取常數就好
10/25 01:04, 8F
‣ 更多 ss455032 的文章
文章代碼(AID): #1PvN3Qu6 (Grad-ProbAsk)
討論串 (同標題文章)
完整討論串 (本文為第 8 之 12 篇)：
排序： 最舊先 | 最新先 | 留言數
在新視窗開啟完整討論串 (共12篇)
‣ 更多 ss455032 的文章
文章代碼(AID): #1PvN3Qu6 (Grad-ProbAsk)