問題タブ [amortized-analysis]

TimeComplexityのドキュメントに見られるように、Python のlist型は配列を使用して実装されています。

したがって、配列が使用されていて、いくつかの追加を行う場合、最終的にスペースを再割り当てし、すべての情報を新しいスペースにコピーする必要があります。
結局のところ、どうすれば O(1) 最悪のケースになるのでしょうか?

最初に n 個の数のセットが与えられたとします。Search()、Predecessor()、および Deletion() クエリをサポートするデータ構造を構築する必要があります。

検索と先行は、最悪の場合、O(ログ処理 n) 時間かかるはずです。削除には償却 O(log n) 時間かかります。許可される事前時間は O(n) です。最初は O(n) のスペースがあります。しかし、どの段階でも、構造内に m 個の数値がある場合、使用されるスペースは O(m) である必要があります。

この問題は RBT を使用して簡単に解決できますが、配列のみを使用するデータ構造が必要です。配列を使用した RBT の実装は必要ありません。データ構造では、ツリーから着想を得たアルゴリズムを使用しないでください。そのようなデータ構造を考えられる人はいますか?

i が正確に 3 の累乗である場合、i 番目の操作のコストが i であり、そうでない場合は 1 であるデータ構造に対する n 操作のシーケンスで、操作ごとの償却コストを見つけようとしています。

誰も私に問題を解決する方法を説明できますか

O(6) を見つけました。それが正しいか間違っているかわかりません。

一連の n 操作が実行されるデータ構造を検討するように求める調査中に、この問題に遭遇しました。k 番目の操作のコストが完全平方の場合は k、それ以外の場合は 1 である場合、操作の総コストと各操作の償却コストはいくらか。

合計が何をもたらすかを確認できる完全な正方形の定義を提供する合計式を考え出すのに少し苦労しています。何か考え/アドバイスはありますか？

私はアルゴリズム分析を学んでいますが、問題に遭遇しました。

私がやった事

各ツリーの各ノードがランダムな値を持つ、ランダムなサイズの 30 個のバイナリ ツリーを生成するプログラムを作成しました。償却分析を使用するために、次のようにツリーの各ノードに（必要に応じて）ランクを割り当てました

「 ノードのランクが r の場合、その左の子のランクは r −1 で、右の子のランクは r + 1 です。」

ここで、各ノードの償却後の複雑さを定義するために、次の式を C++ コードに変換しました

"ai = ti + Φ(Si) − Φ(Si−1)" ここで、Si−1 は i 番目の呼び出しが開始される直前の D の状態であり、Si は呼び出しが終了した直後の D の状態です。

残っているもの

実験結果を償却分析の推定と比較する必要があります。

私はこの部分で盲目で、何をすべきかわかりません。それが得意な人か、私を正しい方向に押してください。私はどこにも助けを見つけることができません。

n 個の単一ノード ツリーがあり、m 個の集合演算が見つかり (注: 結合が以前に行われたと仮定すると、結合はありません)、パス圧縮のみを使用する場合、これには O(m) 時間がかかるというのは本当ですか? 私はこれを証明しようとしてきましたが、そうではないようです。ユニオンはランクによるユニオンを使用しなかったため、検索セットには最大で O(n) の時間がかかる場合があります。しかし、m 個の検索セットを O(m) 時間で実行することはまだ可能ですか?

x を空の配列のサイズとします。配列がいっぱいになると、長さが k > x の新しい配列が作成されます。古い配列の内容が新しい配列にコピーされ、新しい要素も格納されます。

• 長さ k の配列が k ステップで作成されます
• 要素のコピーには一定の時間がかかります。

質問: 各挿入操作が一定の時間を償却し、n 個の要素の挿入に Θ(n) かかるように、どのように k を選択しますか? 選択した結果、挿入操作ごとに一定の償却時間が得られるという仮定を、償却分析で証明してください。

私の直感では、k = 2*n は良いアイデアだと思いますが、それを証明する方法がわかりません。私は償却分析をまったく理解していなかったと思います。助言がありますか？