作者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