algorithm - 使用栈实现队列

Question

这是作业中的问题:

Implement a FIFO queue using two stacks.

The total running time of Enqueue and Dequeue functions should be O(n) in the worst case scenario. Also, analyze the running time of the algorithm.

我做了什么:

void Enqueue(T *value)
{
s1.Push(value);
}

T *Dequeue()
{
    if (s2.size > 0)
        return s2.Pop();
    else if (s1.size > 0)
    {
        for (int i = 0; i < s1.size; i++)
            s2.Push(s1.Pop());

        return s2.Pop();
    }
    else return NULL;
}

算法分析:

一个Enqueue的运行时间是Theta(1)。所有 Enqueue 函数的总运行时间为 n * Theta(1) = Theta(n)。

Dequeue 在最坏情况下的运行时间是 Theta(n)(当您在最后一个 Enqueue 之后调用它时，即当所有项目都插入时)。在所有其他情况下，运行时间为 Theta(1)。

因此，总运行时间为:O(n) + O(n) + n * O(1) = 3 * O(n) = O(n)

这是正确的吗？

Answer 1

So, the total running time is: O(n) + O(n) + n * O(1) = 3 * O(n) = O(n)

您的方向是正确的，但您通常不分析“总运行时间”，而是将其拆分为摊销平均值、最坏情况和最佳情况 - 并对每个操作进行分析。

在你的算法中，很容易看出:

• enqueue() 在所有情况下都在 Theta(1) 中运行。
• dequeue() 在 Theta(n) 最坏情况和 Theta(1) 最好情况下运行。

不，对于棘手的部分 - 我们需要分析 dequeue() 摊销分析。

首先，请注意，在每个 Theta(n)(最坏情况)之前，dequeue() 您必须清空列表，并插入 n元素。
这意味着，为了使最坏的情况发生，您必须至少完成 n enqueue() 操作，每个 Theta(1) 。

这为我们提供了摊销时间:

T(n) = (n*CONST1      +    CONST2*n)             /(n+1)
          ^                 ^                      ^
     n enqueues      1 "espansive" dequeue        #operations

很容易看出 T(n) 在 Theta(1) 中，为您提供 Theta(1) 摊销时间复杂度.

---

tl;博士:

入队:Theta(1) 所有情况
出列:Theta(1) 摊销，Theta(n) 最坏情况