→ dy957:謝謝 我來研究研究! 01/27 23:33
→ dy957:原來那個是它的定義 會了! 01/28 00:16
※ 引述《dy957 (dy957)》之銘言：
: http://www.lib.nctu.edu.tw/n_exam/exam98/cslz/cslz1001.pdf
: 想請問第二題的(1)(2)
: (1)我一直trace不出來 (2)不會
: 還有最後的MIN-CUT大題
: 和Amortized analysis 大題
這題我的亂解如下：
(9)
let ^c_i = c_i + Φ(D_i) - Φ(D_i-1) (會有其他可能的定義嗎？）
因此可以推得Σ(^c_i - c_i) = Φ(D_i) - Φ(D_0) = 2^i - 2^(ceil(logi))
(10)
^c_i = c_i + Φ(D_i) - Φ(D_i-1) = ci + 2 - 2^(ceil(logi)) + 2^(ceil(log(i-1)))
觀察後兩項，if i-1是2的次方，則兩個值會差一，否則兩值相同
加上原題條件可以得到
^c_i = i + 1 if i - 1 is an exact power of 2
= 3 otherwise
: 幾乎都不會冏..
我也好多都不會 囧
: 拜託各位了, 謝謝!
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 122.127.177.56