7

2つのセットAとBが与えられた場合、それらの和集合を見つけるために使用される一般的なアルゴリズムは何ですか、そしてそれは実行時間ですか？

私の直感：

a = set((1, 2, 3))
b = set((2, 3, 5))
union = set()
for el in a:
    union.add(el)

for el in b:
    union.add(el)

Addは、O（1）である衝突のチェックを追加してから、（??）である要素を追加します。これはn回行われます（nは| a | + | b |）。したがって、これはO（n * x）です。ここで、xは追加操作の平均実行時間です。

これは正しいです？

4

4 に答える 4

5

add / find（collision）の複雑さは、unionの実装に依存します。

ハッシュテーブルベースのデータ構造を使用している場合、優れたハッシュ関数を想定すると、衝突操作は実際に一定になります。

それ以外の場合、追加は、ソートされたリスト/ツリーデータ構造の場合はおそらくO（Log（N））になります。

于 2008-11-24T04:54:02.427 に答える
4

最初の答え:数値のセットを扱っている場合、セットを個別の要素の並べ替えられたベクトルとして実装できます。次に、union(S1, S2) を単純にマージ操作 (重複のチェック) として実装できます。これには O(n) 時間がかかります。ここで、n = カーディナリティの合計です。

さて、私の最初の答えは少し素朴です。Akusete の言うとおりです。セットをハッシュ テーブルとして実装できますし、実装する必要があります (セットは汎用コンテナーである必要があり、すべてのオブジェクトを並べ替えることができるわけではありません!)。次に、検索と挿入の両方が O(1) であり、ご想像のとおり、結合には O(n) の時間がかかります。

(あなたの Python コードを見てください) Python セットはハッシュ テーブルで実装されています。この興味深いスレッドを読んでください。代わりにソートされたベクトルを使用するこの実装も参照してください。

于 2008-11-24T05:07:59.823 に答える
3

これは実装に大きく依存します。他の人は、同等のもの (ソート用の未満を持つ) またはハッシュ可能なもの (ハッシュ用の優れたハッシュ関数を持つ) に基づくセットについて言及しています。別の可能な実装には、通常のセット操作の特殊なサブセットのみをサポートするが非常に高速な「union-find」が含まれます (ユニオンは一定の時間で償却されると思いますか?)。

http://en.wikipedia.org/wiki/Union_find

ここでアプリケーションの例を参照してください

http://lorgonblog.spaces.live.com/blog/cns!701679AD17B6D310!220.entry

于 2008-11-24T06:54:20.200 に答える
0

ビットセットを使用できる場合 (int の配列の各ビットがセットの項目に等しい)、単に int 配列と要素の OR をたどることができます。これには、複雑さ O(N) (N は配列の長さ) または O((m+31)/32) (M はアイテムの数) があります。

于 2008-11-24T10:00:24.677 に答える