問題タブ [amortized-analysis]

リンクされたリスト表現を使用して各セットを表すとします。各ノードには、値、次のポインター、およびセットの代表へのポインターという 3 つのフィールドがあります。ヘッド、テール、カウント (セット内の要素の数) の 3 つのフィールドを持つ各セットの 1 つのインデックス オブジェクト (または代表) を維持します。

セットのユニオンの場合、要素ごとに新しいセットを作成し、それらのユニオンを取る必要があります。

n 要素の各作成操作には O(1) 時間がかかるため、合計 = O(n) です。

ここで、ユニオン中に、カウント数の少ないセットがカウント数の多いセットに追加されるように要素を結合します。そのため、n 個のセットの結合の時間計算量は O(n) かかります。

総時間計算量 = O(n) + O(n) /2n = O(1)。

したがって、私によると、ユニオン操作の時間の複雑さは O(1) である必要がありますが、どこでも O(n) と書かれています。なぜそうなのですか？

アルゴリズムを分析する方法を学んでいて、「償却時間」という表記を見つけました。次のような事前定義された見積もりがいくつか見つかりました。

-ソートされた配列への挿入の償却時間: O(n)

また、ソートされた配列からの削除の償却時間は次のとおりです: O(1)

誰か詳しく説明してくれませんか！

分析を償却して、後継関数 (inorder アルゴリズムで次の要素を見つける関数) が平均 O(1) であることを証明するにはどうすればよいですか? 後継関数が最後に見つかった要素で動作していると仮定します。それは O(1) ですか？O(log n)ですか？

バランスの取れた bst の後継関数の償却された実行時間のケースを作成する必要があります。最下位の葉から開始し、「最大」ノードに移動することがシーケンスである場合、T(n)/n => O(n)/n = であるため、平均実行時間は O(1) であることを知っています。 > O(1)

しかし、シーケンスが最長でない場合に何が起こるかはわかりません。その点については、喜んでお手伝いさせていただきます。