Amortized Cost for an incrementing 做账分摊法小结 ◆ Actual cost 啼可以为不同的操作赋予不同的分摊成本 sEveral 1 to O flips plus 1 flip of 0 to1 分摊成本与实际成本要满足分摊约束条件 Amortized cost 啼分摊的经验 n0+1*2=2 如果一个操作的作用可以被另外一个或几个操 作消除,则可以把消除函数的实际成本分摊到 比操作本身,而其消除操作的分摊成本为0 匕复杂情况可以通过上述情况的方程式进行求解 The potential method 势方法 The potential method represent the m Start with an initial data structure Do prepaid work as credit stored with the wOn which there are n operations being specific objects in the data structure. We performed call the prepaid work as"potential energy c After each operation the data structure or just the "potential change to D 转下页 势方法(续 如何理解势方法 a D R 势方法适合那种有状态的数据结构上的各 B Actual cost is c. amortized cost is a. then 种操作成本的分摊 啼a1=c+d①)-ΦD1) 啼每个操作的分摊成本是 Require b①D)-D≥0 区实际成本十势能的增加 以上分摊成本可以理解为,一个操作不仅 要为自己付帐,同时要为自己对环境的影 响而付帐【可能是收益】4 清华大学 宋斌恒 19 Amortized Cost for an incrementing Actual cost Several 1 to 0 flips plus 1 flip of 0 to1 Amortized cost n*0+1*2=2 清华大学 宋斌恒 20 做账分摊法小结 可以为不同的操作赋予不同的分摊成本 分摊成本与实际成本要满足分摊约束条件 分摊的经验 如果一个操作的作用可以被另外一个或几个操 作消除，则可以把消除函数的实际成本分摊到 此操作本身，而其消除操作的分摊成本为0 复杂情况可以通过上述情况的方程式进行求解 清华大学 宋斌恒 21 The potential method The potential method The potential method represent the prepaid work as credit stored with the specific objects in the data structure. We call the prepaid work as “potential energy” or just the “potential” 清华大学 宋斌恒 22 势方法 Start with an initial data structure D0 On which there are n operations being performed After each operation the data structure change to Di 转下页 清华大学 宋斌恒 23 势方法（续） Φ: Di ÆR Actual cost is ci , amortized cost is ai then ai =ci + Φ(Di ) – Φ(Di-1) Require Φ(Di ) – Φ(D0) ≥ 0 清华大学 宋斌恒 24 如何理解势方法 势方法适合那种有状态的数据结构上的各 种操作成本的分摊 每个操作的分摊成本是 实际成本＋势能的增加 以上分摊成本可以理解为，一个操作不仅 要为自己付帐，同时要为自己对环境的影 响而付帐【可能是收益】