特殊的栈操作会带来不可接受的复杂度吗？ ·分析各个操作的实际代价： PUSH 1 POP 1 MULTIPOP min(k,s) ·赋予各个操作摊还代价： PUSH 2 如何初始设置摊还代价？ POP 如何进行核算？ MULTIPOP 0
特殊的栈操作会带来不可接受的复杂度吗？ • 分析各个操作的实际代价： • 赋予各个操作摊还代价： 如何初始设置摊还代价？ 如何进行核算？
如何核算、优化？ ·分析操作序列，其摊还总代价是否总是大于实际代价 ·如果可能小于，增加某个操作的摊还代价 ·如果正向gap过大，降低某个操作的摊还代价 ·找到一个合适的摊还代价分配，计算总摊还代价，以此为解 ∑e≥2c =1
如何核算、优化？ • 分析操作序列，其摊还总代价是否总是大于实际代价 • 如果可能小于，增加某个操作的摊还代价 • 如果正向gap过大，降低某个操作的摊还代价 • 找到一个合适的摊还代价分配，计算总摊还代价，以此为解