4

次のプロパティを持つデータ構造が必要になることがよくあります。

  • O(n) の n 個のオブジェクトの配列で初期化できます。
  • O（1）でランダムな要素を取得できます。この操作の後、選択された要素は構造から削除されます。(交換なし)
  • O(p) で p 個の「置換なしの選択」操作を元に戻すことができます
  • O(log(n)) の構造から特定のオブジェクトを (たとえば id で) 削除できます。
  • 現在構造体にあるオブジェクトの配列を O(n) で取得できます。

他のアクション (挿入など) の複雑さ (または可能性) は問題ではありません。複雑さに加えて、n の数が少ない場合にも効率的である必要があります。

そのような構造を実装するためのガイドラインを誰か教えてもらえますか? 私は現在、上記のすべてのプロパティを持つ構造を実装していますが、要素の選択は過去の選択回数 d で O(d) を取ります (「まだ選択されていない」かどうかを明示的にチェックするため)。O(1) でのピッキングを可能にする構造を理解することはできますが、これらは他の操作の少なくとも 1 つでより複雑です。

ところで: 上記の O(1) は、複雑さが以前に選択された要素とは無関係であり、合計の要素とは無関係であることを意味することに注意してください。

*モンテカルロ アルゴリズム (n 個の要素の「セット」から p 個のランダムな要素を繰り返し選択する)。

4

4 に答える 4

2

HashMap の複雑さは、挿入と削除の両方で O(1) です。多くの操作を指定しますが、それらはすべて挿入、削除、トラバースに他なりません。

O(n) の n 個のオブジェクトの配列で初期化できます。

n * O(1) 挿入。HashMap は問題ありません

O（1）でランダムな要素を取得できます。この操作の後、選択された要素は構造から削除されます。(交換なし)

これは、O(n) を必要とする唯一の op です。

O(p) で p 個の「置換なしの選択」操作を元に戻すことができます

これは挿入操作です: O(1)。

O(log(n)) の構造から特定のオブジェクトを (たとえば id で) 削除できます。

O(1)。

現在構造体にあるオブジェクトの配列を O(n) で取得できます。

O(n) で HashMap をトラバースできます

編集: O(n) でランダムな要素をピックアップする例:

HashMap map ....
int randomIntFromZeroToYouHashMapSize = ...
Collection collection = map.values();
Object[] values = collection.toArray();
values[randomIntFromZeroToYouHashMapSize];
于 2011-07-01T00:29:52.553 に答える
1

O(1) ランダム ルックアップを取得するための簡単な修正を加えた0verboseと同じ回答です。同じ n 個のオブジェクトを格納する配列を作成します。次に、HashMap にペアを格納します。たとえば、オブジェクト (簡単にするために文字列) が次のようになっているとします。

{"abc" , "def", "ghi"}

を作成する

List<String> array = ArrayList<String>("abc","def","ghi")

次の値で HashMap マップを作成します。

for (int i = 0; i < array.size(); i++) 
{
    map.put(array[i],i);
}

O(1) ランダム ルックアップは、配列内の任意のインデックスを選択することで簡単に実現できます。発生する唯一の問題は、オブジェクトを削除するときです。そのためには、次のようにします。

  1. でオブジェクトを検索しますmap。その配列インデックスを取得します。このインデックスをi( map.get(i)) - O(1)と呼びましょう

  2. array[i] を array[size of array - 1] (配列の最後の要素) と交換します。配列のサイズを 1 減らします (数値が 1 つ少ないため) - O(1)

  3. (map.put(array[i], i)) - O(1)iの配列の位置にある新しいオブジェクトのインデックスを更新しますmap

Java と cpp 表記が混在していることをお詫びします。

于 2011-07-01T03:47:38.430 に答える
1

Collections.shuffle()での使用に関する私の分析は次のArrayListとおりです。

  • ✔ は、O(n) の n 個のオブジェクトの配列で初期化できます。

    はい。n が事前にわからない限り、コストは償却されます。

  • ✔ O(1) でランダムな要素を取得できます。この操作の後、選択された要素は置換なしで構造から削除されます。

    はい、シャッフルされた配列の最後の要素を選択します。subList()配列を残りの要素のa に置き換えます。

  • ✔ O(p) で p 個の「置換なしの選択」操作を元に戻すことができます。

    はい、 を介してこのリストの最後に要素を追加しますadd()。

  • ❍ O(log(n)) の構造から特定のオブジェクトを (たとえば id によって) 削除できます。

    いいえ、O(n) のように見えます。

  • ✔ O(n) で現在構造体にあるオブジェクトの配列を取得できます。

    はい、使用toArray()は妥当に見えます。

于 2011-07-01T02:18:37.713 に答える
1

ArrayList「選択された」と「選択されていない」に分割された配列 (または ) はどうですか? 境界がどこにあるかを追跡し、選択するには、境界の下にランダムなインデックスを生成します。次に (順序は気にしないため)、そのインデックスのアイテムを最後に選択されていないアイテムと交換し、境界を減らします。 . 選択を解除するには、境界をインクリメントするだけです。

更新: O(log(n)) の削除を忘れていました。HashMapただし、 ID をインデックスに保持する場合は、それほど難しくはありませんが、メモリを少し消費します。

オンラインで調べてみるとIndexedHashSet、多かれ少なかれこの原則に基づいてすべてが機能するさまざまな実装を見つけることができます。ArrayListHashMap

（ただし、よりエレガントなソリューションがあれば、ぜひ見てみたいです。）

更新 2:うーん... または、配列を再コピーするか移動する必要がある場合、実際の削除は再び O(n) になりますか?

于 2011-07-01T01:10:58.900 に答える