核算方法accounting ·核算法的基本思想 ·我们不便或者难以全局观测合计代价的前提下，可以从微观出发，考察 每个操作的代价 ·测算每个动作的实际代价 ·赋予（且通过核算不断优化）每个动作的摊还代价 ·核算依据： 如果左式始终 e≥∑c 成立，其左部 i=】 =】 有何意义？ 总摊还代价不断逼近实际代价
核算方法accounting • 核算法的基本思想 • 我们不便或者难以全局观测合计代价的前提下，可以从微观出发，考察 每个操作的代价 • 测算每个动作的实际代价 • 赋予(且通过核算不断优化)每个动作的摊还代价 • 核算依据： 总摊还代价不断逼近实际代价 如果左式始终 成立，其左部 有何意义？
特殊的栈操作会带来不可接受的复杂度吗？ ·分析各个操作的实际代价： PUSH 1 POP 1 MULTIPOP min(k,s) ·赋予各个操作摊还代价： PUSH 2 如何初始设置摊还代价？ POP 如何进行核算？ MULTIPOP 0
特殊的栈操作会带来不可接受的复杂度吗？ • 分析各个操作的实际代价： • 赋予各个操作摊还代价： 如何初始设置摊还代价？ 如何进行核算？
如何核算、优化？ ·分析操作序列，其摊还总代价是否总是大于实际代价 ·如果可能小于，增加某个操作的摊还代价 ·如果正向gap过大，降低某个操作的摊还代价 ·找到一个合适的摊还代价分配，计算总摊还代价，以此为解 ∑e≥2c =1
如何核算、优化？ • 分析操作序列，其摊还总代价是否总是大于实际代价 • 如果可能小于，增加某个操作的摊还代价 • 如果正向gap过大，降低某个操作的摊还代价 • 找到一个合适的摊还代价分配，计算总摊还代价，以此为解