作者trovadores (吟遊詩人)
看板Grad-ProbAsk
標題Re: [理工] [資結]-交大98-資聯 - Amrtized cost
時間Sun Jan 31 00:24:23 2010
※ 引述《chaly77714 (Chaly)》之銘言：
: 附上98交大的題目
: http://www2.lib.nctu.edu.tw/n_exam/exam98/cslz/cslz1001.pdf
: 演算法的最後一題考Amrtized cost
: 有稍微看了一下課本
: 但還是不太了解
: 不知是否有人可以解釋一下
: 該題該如何解嗎???
我的想法 不知道正不正確
第一小題代課本公式17.3 (p.413)
Σaci= Σci + Φ(Dn)-Φ(D0)
Σci移到左邊變 Σ(aci-ci)
右邊題目有Φ(D0)代0
所以答案應該是Φ(Dn)
第二小題代課本公式17.2
aci = ci + Φ(Di)-Φ(Di-1)
ci有兩個case所以aci也有兩個case
將題目給的potential function 定義代入即可
僅供參考>"<
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 114.40.84.88
※ 編輯: trovadores 來自: 114.40.69.74 (01/31 01:29)
1F：→ chaly77714:謝謝 我研究一下 02/02 13:11
2F：推 assassin88:請問第二小題有答案嗎? 02/04 22:56