algorithm - 多重流行和摊销

Question

现在我正在学习会计摊销。在许多教科书和网站中有一个例子，他们用堆栈的多弹出方法教授会计摊销。堆栈操作的文字成本 where ''' Push: 1 Pop: 1 Multipop: min(stack.size, k) ''' 我理解这些操作成本，但是示例总是转移到将摊销成本分配给那些功能总是 ''' Push: 2 Pop: 0 Multipop: 0 ''' 为什么在分配成本时是 push 2？为什么pop和multi pop都是0？multi pop 不会比 push 有更大的价值吗？

谢谢您的帮助。

标签： algorithmamortized-analysis

Answer 1

摊销的秘密在于实际成本不再与摊销成本完全对应。除了不能破产之外，没有确定操作如何摊销的通用方法，因此如果您愿意，可以将 multi-pop 的摊销成本设为 5。

在此示例中，您可以想象，每当我们推送一个元素（成本 1）时，我们还购买了一张用于弹出该元素的优惠券（成本 1，因此 1 + 1 = 摊销成本 2，因为我们做了一个工作单元并预付了其他）。然后我们只使用代金券支付流行音乐，所以流行音乐和多流行音乐都是免费的。