1

この質問に出くわしたとき - using two stacks to implement a queue、その複雑さを分析する方法を考えています。

これを例にとります：

  • queue() の場合、単純に受信トレイにプッシュされるため、複雑さは常に O(1) です。
  • dequeue() の場合、ほとんどの場合、複雑さも O(1) ですが、outbox が空の場合、すべての要素を inbox から outbox に移動するループが必要です。では、この操作の複雑さは何ですか?

そのような問題を分析するときのアイデアは何ですか？

4

1 に答える 1

0

Dave L.が彼の説明で述べているように、「各要素は2回プッシュされ、2回ポップされ、償却された一定時間の操作が行われます」。これは、あるスタックから別のスタックに n 個の要素を移動する必要がある各デキュー (O(n) 時間かかる) の後に、O(1) 時間しかかからない n-1 回のデキューが続くためです。

の複雑さを表現する 1 つの方法はdequeue()、O(1) の最良のケースと O(n) の最悪のケースで一定の時間を償却したと言うでしょう。

于 2014-05-06T15:27:15.047 に答える