1

私の宿題は、次のアルゴリズムの最悪の場合の実行時間を決定することです。エンキューは簡単です。それはただ一定です（そうでなければ、私は愚かに感じるでしょう）

2つ目は紛らわしいです。昨日も同様の質問をしたのですが、とても参考になる回答がたくさんありました。がんばります。 

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

これを調べる 1 つの方法は、プッシュとポップの数を数えることです。キューに n 個の要素がある場合、実装は n 個のプッシュと n 個のポップを実行して に転送inしoutます。次に、最後の要素を取り除くために 1 つの pop を実行し、次に n - 1 回のプッシュと n - 1 回の pop を実行して にout戻しますin。これは合計 Θ(n) 回のプッシュとポップです。各プッシュとポップには Θ(1) 時間かかる (または、少なくとも n 回のプッシュと n ポップには Θ(n) 時間かかる) ため、スタック操作で行われる合計作業は Θ(n) です。また、エラー処理などのために O(1) の余分な作業が行われます。したがって、行われる作業の合計は Θ(n) です。

お役に立てれば！

于 2013-10-21T01:09:20.187 に答える
0

リンクされたリストの先頭からノードを削除するには、一定の時間がかかります。ただし、リンクされたリストの最後のノードを見つけるには線形時間がかかります (それへの参照を注意深く維持しない限り)。

于 2014-02-09T07:26:02.877 に答える