Re: [請益] 好題目q:

看板ACMCLUB作者時間19年前 (2006/07/07 21:01), 編輯推噓0(0推 0噓 0→)
留言0則, 0人參與, 最新討論串3/3 (看更多)
→
07/07 15:40, , 1F
To sophialiege: 「隨機客」想不出來怎麼做O(1)-time update
07/07 15:40, 1F
→
07/07 15:40, , 2F
可以請sophialiege解釋一下嗎？
07/07 15:40, 2F
結論: 抱歉想錯了,如果有興趣可以往下看 因為 dptable [i][j] 可能從 dptable[1..i-1][j-1] 來 update 而且當 dptable [i][j] 是由 dptable[u][j-1] 來 update 時 dptable[i+1][j] 就不可能是由 dptable[1..u-1][j-1] 來 update 到目前為止都對,這時想用Amortized Analysis來定time complexity是constant 這時還需要證明 dptable[1..i-1][j-1] + compensate[1..i-1][i] 是 U 形 curve 1. dptable[1..i-1][j-1] 是 non-decreasing sequence 2. compensate[1..i-1][i] 是 non-increasing sequence 由於當時天真地以為 (1) (2) 可以導出 U 形 curve的結論, so ... -- ※ 發信站: 批踢踢兔(ptt2.cc) ◆ From: 140.112.250.175
‣ 更多 sophialiege. 的文章
文章代碼(AID): #14hbiQ00 (ACMCLUB)
‣ 更多 sophialiege. 的文章
文章代碼(AID): #14hbiQ00 (ACMCLUB)