algorithm - 使用 3 个堆栈实现 Deque(摊销时间 O(1))

Question

我有一个关于 howmework 的问题:

使用 3 个堆栈实现双端队列。 Deque 有这些操作:InsertHead、InsertTail、DeleteHead、DeleteTail。证明每个操作的摊销时间为O(1)。

我所尝试的是将问题视为河内问题。
因此，让我们将堆栈称为:L(左)、M(中)、R(右)。

伪代码实现:

InsertHead(e):
     L.push(e);

DeleteHead(e):
     L is empty:

       while R is not empty:
          pop and insert the element to M;
       pop M;
       while M is not empty:
         pop and insert the element to R;

     L is not empty:    
       L.pop(e);

InsertTail 和 DeleteTail 与上述实现的原理相同。
我如何证明摊销时间是 O(1)？
因为 L 中可以有 N 个元素，并且 wile 循环将花费 O(n)，现在如果我调用 deleteHead N 次来计算分摊时间，复杂度不会是 O(n^2)？

有人可以帮助我如何证明上述实现在摊销时间内需要 O(1) 吗？

Answer 1

我们继续使用 potential method ;定义
Phi = C |L.size - R.size|
对于一些常数 C稍后我们将为其选择一个值。让 Phi_t表示t之后的电位操作。请注意，在两个堆栈大小相等的“平衡”状态下，数据结构的电位为 0。

任何时候的电位都是每个堆栈中元素数量差异的常数倍。请注意 Phi_0 = 0所以当结构初始化时电位为零。

很明显，推送操作最多增加了C 的潜力。 .一个不会丢失的弹出操作(即相关堆栈非空的地方)也会改变电位至多 C .这两个操作的真实成本均为 1，因此它们的摊销成本 1 + C .

当弹出操作发生并导致未命中时(当我们要弹出的堆栈为空时)，该操作的真实成本为 1 + 3/2 * R.size当我们试图从 L 弹出时，反之亦然，当我们从 R 弹出时.这是因为我们将 R 的一半元素移到 M 并返回，而 R 的另一半元素移到 L。+1需要，因为来自 L 的最后一次弹出在此重新平衡操作完成后。

因此，如果我们取 C := 3/2 ，则发生未命中时的弹出操作已摊销成本 1，因为潜力从 3/2 * R.size 减少由于重新平衡而变为 0，然后我们可能会产生 3/2 的额外费用来自重新平衡后发生的流行音乐。

换句话说，每个操作都有一个以常数为界的摊销成本。

最后，由于初始势为 0，且势始终为非负，因此根据需要，每个操作的摊销成本为 O(1)。