讨论 小结 长整数二进制加法的线性性证明 当聚集分析方法关键点 ?高位相加快?低位相加快?或者一样? 所有n个运算集中考虑 考虑不同运算的消费不同 只考虑所有运算的总复杂度 最后分摊到每个运算 The accounting method Stack operation o In the accounting method we assign The actual cost of operations were different amortized cost for different PUsh operations, some of the amortized cost less or greater than its actual cost. CLet a be the amortized cost for the ith Amortized cost operation and C is its actual cost than it APush 2 should satisfies for all n.【分摊约束条件】 花”账中成本的含义 Amortized analysis for cementing the binary counter Push的实际成本为1,同时为其在Pop时花 4 Actual cost for a flip 的费用存入资金1,故其分摊成本为2。 aSet a bit from o to 1 cost 1 dollar Pop的实际成本为1,但是由于已经预付, aSet a bit from 1 to 0 cost 1 dolla 故其分摊成本为0。 Amortized cost for a flip MultiHop的实际成本为m,但由于已经预 ASet a bit from 0 to 1 cost 2 dollar, pay for its 付,故其分摊成本为0。 reverse transfer ASet a bit from 1 to o cost o dollar. because it is paid already3 清华大学 宋斌恒 13 讨论 长整数二进制加法的线性性证明： ？高位相加快？低位相加快？或者一样？ 清华大学 宋斌恒 14 小结 聚集分析方法关键点 所有n个运算集中考虑 不考虑不同运算的消费不同 只考虑所有运算的总复杂度 最后分摊到每个运算 清华大学 宋斌恒 15 The accounting method The accounting method In the accounting method we assign different amortized cost for different operations, some of the amortized cost is less or greater than its actual cost. Let ai be the amortized cost for the ith operation and ci is its actual cost than it should satisfies for all n. 【分摊约束条件】 ∑ ∑ = = ≥ n i i n i i a c 1 1 清华大学 宋斌恒 16 Stack operation Stack operation The actual cost of operations were Push 1 Pop 1 Multipop min{k, s} Amortized cost Push 2 Pop 0 Multipop 0 清华大学 宋斌恒 17 “花”账中成本的含义 Push 的实际成本为1，同时为其在Pop时花 的费用存入资金1，故其分摊成本为2。 Pop 的实际成本为1，但是由于已经预付， 故其分摊成本为0。 MultiPop的实际成本为m，但由于已经预 付，故其分摊成本为0。 清华大学 宋斌恒 18 Amortized analysis for Amortized analysis for incrementing the binary counter incrementing the binary counter Actual cost for a flip Set a bit from 0 to 1 cost 1 dollar. Set a bit from 1 to 0 cost 1 dollar. Amortized cost for a flip Set a bit from 0 to 1 cost 2 dollar, pay for its reverse transfer. Set a bit from 1 to 0 cost 0 dollar, because it is paid already