→ hil:To sophialiege: 「隨機客」想不出來怎麼做O(1)-time update推 07/07 15:40
→ hil:可以請sophialiege解釋一下嗎？推 07/07 15:40
結論: 抱歉想錯了,如果有興趣可以往下看
因為 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