StackQueue摊销时间实现

Question

根据下面引号中的规范，实现了一个队列（该语言使用Ruby，但希望每个人都能读懂）。

使用堆栈实现队列。也就是说，只使用push和pop操作来写入队列和出队列。

就性能而言，enqueue应该是O(1)，但dequeue在最坏的情况下可能是O(n)。从时间上看，出队时间应为O(1)。证明您的解决方案实现了这一点。

class StackQueue
  def initialize
    @in, @out = [], []
  end

  def enqueue(value)
    @in << value
  end

  def dequeue
    if @out.empty?
      @out << @in.pop until @in.empty?
    end

    @out.pop
  end
end

我在想，你怎么证明排队的摊销时间？谢了！

Answer 1

直观地讲，O(1)摊销的复杂性很容易理解：我们出列的每个元素都被推送到中精确地一次，从中精确地弹出一次，推送到out精确地一次，从out精确地弹出一次，所有这些都是O(1)操作。

用势法很容易证明。每当我们排队一个值时，我们为推入的成本“支付”3：1的费用，为将来转移到out节省2的费用。

我们还可以用3:1emptytest，1poponout，1in为空来支付出队列费用。我们可以用我们在enqueue中节省的盈余来支付每次poponin和pushonout的费用。

我们可以通过为每个操作“支付”3来负担所有操作，给出一个O(1)的摊销复杂度。