1

我的作业要求我确定以下算法的最坏情况运行时间。入队很容易。那只是恒定的（我希望，否则我会感到愚蠢）

第二个很混乱。我昨天问了一个类似的问题，得到了很多非常有用的答案。我会尽力而为。 

Algorithm enqueue(o)
    in stack.push(o)

Algorithm dequeue()
    while (! in stack.isEmpty()) do    // this just checks for an empty stack, so O(1)
        out stack.push(in stack.pop()) // this do loop runs for as many times as values in the stack, so it is O(N)

    if (out stack.isEmpty()) then
        throw a QueueEmptyException    // this is just an exception, so I assume it is O(1) 

    return_obj ←  out stack.pop()      // I think the rest of the program is linear.
                                       // Although without actually coding it out, I'm not 100% sure I even understand what it does.
    while (! out stack.isEmpty()) do

    in stack.push(out stack.pop())
    return return_obj;
4

2 回答 2

2

一种看待这种情况的方法是计算推送和弹出的次数。如果您的队列中有 n 个元素，则实现将执行 n 次推送和 n 次弹出以转移in到out. 然后它会执行一次 pop 以摆脱最后一个元素，然后再进行 n - 1 次 push 和 n - 1 次 pop 以out放回in. 这是总共 Θ(n) 的 push 和 pop。每个 push 和 pop 需要 Θ(1) 时间（或者至少 n 次 push 和 n pops 需要 Θ(n) 时间），因此堆栈操作完成的总工作量是 Θ(n)。那里还有 O(1) 的额外工作用于错误处理等。因此，完成的总工作是 Θ(n)。

希望这可以帮助！

于 2013-10-21T01:09:20.187 回答
0

从链表的前面删除一个节点需要恒定的时间。然而，找到链表的最后一个节点需要线性时间（除非我们小心维护对它的引用）。

于 2014-02-09T07:26:02.877 回答