4

我对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) 吗？

Deque from 3 Stacks：Deque的DeleteHead操作

4

1 回答 1

1

我们继续使用潜在方法；定义

Phi = C |L.size - R.size|

对于一些常量C，我们稍后会为其选择一个值。让Phi_t表示操作后的潜力t。请注意，在两个堆栈大小相等的“平衡”状态下，数据结构的电位为 0。

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

很明显，push 操作最多会增加 0 倍的潜力C。不会丢失的弹出操作（即相关堆栈非空）也最多将电位改变C. 这两个操作都具有真实成本 1，因此它们具有摊销成本1 + C。

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

因此，如果我们取，则发生未命中C := 3/2时的弹出操作的摊销成本为 1，因为由于重新平衡，潜力从减少到 0，然后我们可能会在重新平衡后发生的弹出操作中产生额外的成本。3/2 * R.size3/2

换句话说，每个操作都有一个由常数限制的摊销成本。

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

于 2020-04-22T10:28:40.270 回答