algorithm - 在摊销分析中使用潜力和会计方法

Question

我已经阅读了有关会计和潜在方法的信息，但我仍然无法解决这些问题：

标签： algorithmstackqueuetime-complexityamortized-analysis

Answer 1

直觉

通过分析每个操作的昂贵案例和廉价案例，您可以了解如何对每个操作收费（然后您可能需要一些小修复来“修复”数字）

通过查看数据结构的重要参数，您可以构建一个潜在的函数（例如，它是 s2 中元素的数量）

• 此外，在这里看到很多例子真的很有帮助

核算方法：

让每次插入收取两枚硬币：一枚用于从 s2 中弹出元素，第二枚用于将元素插入到 s1 中，每次删除收取一枚硬币，用于从 s1 中删除元素。

然后请注意，银行中的信用不能为负，因为如果 s1 不为空，那么我们只需支付操作的实际成本（这是从 s1 中唯一的删除），如果 s1 为空，那么操作将从 s2 弹出并插入我们已经收费的 s1。（重要的是要注意，我们假设我们从空数据结构开始，或者，我们对数据结构的每个初始状态都获得了适当的信任）

现在您可以看到，对于每组操作，我们的总信用 3n 涵盖了操作的实际成本（我们获得了 s2 中剩余元素的信用边际），因此这些是有效的摊销界限。

为了解决潜在的函数，让我们考虑函数：

势（DataStructure）= 2 * s2 中的元素数

回想一下，我们是这样计算的：

OP.A 的摊余成本 = OP.A 的实际成本 + 潜力(DS after)-潜力(DS before)

所以我们得到（表示 k 中 s2 中的元素数）：

插入： 1 + 2(k+1)-2k = 3

廉价删除： 1 + 2k - 2k = 1

对于昂贵的删除： 1+2k + 0 - 2k = 0（实际成本为 1+2k，因为我们从 s2 弹出并插入每个元素到 s1，然后从 s1 弹出一个元素）