最近、私はインタビューに行き、インタビュアーは私にこの質問をしました.
size の k+1 スタックがあります1, 2^1, 2^2, 2^3, ...,2^k。それぞれ呼びましょうstack 1, stack 2, ... stack k+1。がinsert(x)呼び出されると、要素は最初のスタック、つまりサイズ 1 のスタックに挿入されます。スタックがいっぱいの場合、そのスタックの要素は次のスタックに移動され、要素は最初のスタックに挿入されます。パイプ操作に似ています。スタック 1 は要素をスタック 2 にプッシュし、スタック 2 はスタック 3 などにプッシュします。すべてのスタックがいっぱいになると、スタック オーバーフローを示すエラーがスローされます。別の操作、delete(x) があります。スタックのスタックから x を削除します。したがって、x が最上位の要素ではない場合、つまりスタック 1 に存在しない場合は、そこから要素をポップし、要素をシフトしてから、要素が見つかるまでポップを試みて削除します。この実装の挿入と削除の償却後の複雑さは?
編集 1 : 挿入と削除がどのように機能するかを示します。
それぞれサイズ 2^0 と 2^1 のスタック 1 とスタック 2 の 2 つのスタックがあるとします。
反復 0 : スタック 1 -> {}、スタック 2 -> {}
反復 1 : Insert(1)。スタック 1 -> {1}、スタック 2 -> {}、トップ -> 1
反復 2 : Insert(2)。スタック 1 -> {2}、スタック 2 -> {1}、トップ -> 2
反復 3 : Insert(3)。スタック 1 -> {3}、スタック 2 -> {2,1}、トップ -> 3
反復 4 : Insert(4)。オーバーフロー例外。スタック 1 -> {3}、スタック 2 -> {2,1}、トップ -> 3
反復 5 : delete(2)。
- 2!=3 として 3 をポップして続行します。スタック 1 -> {2}、スタック 2 -> {1}、トップ -> 2
- 2をポップして返します。スタック 1 -> {1}、スタック 2 -> {}、トップ -> 1
反復 6 : Insert(4)。スタック 1 -> {4}、スタック 2 -> {1}、トップ -> 3
両方の操作が明確になったことを願っています :)
私は自分のレベルで最善を尽くしましたが、最悪の場合の時間の複雑さ、つまり1+2^1+2^2+..+2^k(幾何学的進行の合計) しかわかりませんでした。最悪の場合の時間の複雑さを探しているわけではありません。償却された複雑さにさえ到達できませんでした。この問題の償却された複雑さを計算する方法を理解するのに役立つ人はいますか?