使用堆栈实现队列

问题描述

这是作业的问题：

在最坏的情况下，入队和出队功能的总运行时间应为O（n）。另外，分析算法的运行时间。

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;
}

算法分析：

一个队列的运行时间是Theta（1）。所有Enqueue函数的总运行时间为n * Theta（1）= Theta（n）。

Running time of one Enqueue is Theta(1). Total running time of the all Enqueue functions is n * Theta(1) = Theta(n).

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

Running time of Dequeue in worst case scenario is Theta(n) (when you call it after the last Enqueue, i.e. when all the items inserted). In all other cases the running time is Theta(1).

因此，总运行时间为：
O（n）+ O（n）+ n * O（1）= 3 * O（n）= O（n）

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

这是否正确？

推荐答案

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

You're in the right direction, but you usually don't analyze "total running time", you split it to amortized average, worst case, and best case - and analyze it for each operation.

在您的算法中，很容易看到：

In your algorithm, it is easy to see that:

• enqueue（）在所有情况下都在Theta（1）中运行。


• dequeue（）在 Theta（n）最坏的情况下运行，而 Theta（1）最好的情况。

• enqueue() runs in Theta(1) for all cases.
• dequeue() runs in Theta(n) worst case and Theta(1) best case.

不是，对于棘手的部分-我们需要分析 dequeue（）摊销分析。

Noe, for the tricky part - we need to analyzed dequeue() amortised analysis.

首先，请注意在每个 Theta（n ）（最坏的情况）， dequeue（），您必须清空列表，并插入 n 元素。

这意味着，为了使最坏的情况发生，您必须至少完成 n enqueue（）个操作，每个 Theta（1）。

First, note that before each Theta(n) (worst case), dequeue() you must have emptied the list, and inserted n elements.
This means, in order for the worst case to happen, you must have done at least n enqueue() operations, each Theta(1).

这给了我们摊销时间： p>

This gives us amortised time of:

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

很容易看到 T（n）位于 Theta（1）中，为您提供 Theta（1）摊余时间复杂度。

It is easy to see that T(n) is in Theta(1), giving you Theta(1) amortized time complexity.

tl; dr：

排队：Theta（1）所有情况

出队：Theta（1）摊销，Theta（n）最坏情况

enqueue: Theta(1) all cases
dequeue: Theta(1) amortized, Theta(n) worst case

这篇关于使用堆栈实现队列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！