問題タブ [amortized-analysis]

私は独学しているコースに設定された問題から、次の問題に取り組んでいます。

私は最初の部分を解決しました。私は2番目に立ち往生しています。以上が今までの私の考えです。v をルートとするサブツリーを再構築する適切な方法は、それを 1 回トラバースして値を並べ替えられた順序で配列にコピーし、次にもう一度トラバースしてバランスの取れたバイナリ ツリーに構築することだと思います。したがって、これは v.size で線形になります。ただし、ポテンシャルと定数がこれを O(1) に変換できる場所はわかりません。ましてや、そのような定数がアルファにどのように依存するかはわかりません。再構築操作はアルファとは無関係だと思っていたので、アルファは単純に再構築の頻度に影響するのでしょうか? では、アルファはポテンシャル関数から出てくるのでしょうか? そして、cはアルファをキャンセルするのに役立ちますか？もしそうなら、潜在的な関数をどのように書き直すかについて、私はいくつかのガイダンスを得ることができますか?

探している要素が現れる 2^n-1 要素の並べ替えられた配列の二分探索の場合、償却された最悪の場合の時間計算量はどれくらいですか?

これは私の最終試験の復習シートで見つけました。最悪のケースは O(log n) であるため、二分探索に償却された時間の複雑さが必要な理由もわかりません。私のメモによると、償却コストはアルゴリズムの上限を計算し、それをアイテムの数で割るので、最悪の場合の時間の複雑さを n で割ったもの、つまり O(log n )/2^n-1?

参考までに、私が使用している二分探索は次のとおりです。

操作の償却時間が O(1) の場合、最悪の場合、O(N^2) 時間かかることがありますか?

最近、私はインタビューに行き、インタビュアーは私にこの質問をしました.

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(幾何学的進行の合計) しかわかりませんでした。最悪の場合の時間の複雑さを探しているわけではありません。償却された複雑さにさえ到達できませんでした。この問題の償却された複雑さを計算する方法を理解するのに役立つ人はいますか?