3

私の質問は、5 ～ 7 セットの交差をどのように適用できるかということです。各セットに要素のセットがあるとします。このためのアルゴリズムの作成と、このプロセスの複雑さを教えてください。

4

3 に答える 3

2

簡単な方法：

I = S_1;
For each set s in S_2 ... S_N:
    For each element ei in I:
      if ei not in s
        remove ei from I
      endif
    endfor
endfor

これにより、各セットに m 個の要素があり、N 個のセットがある場合、複雑さは m^2xN になります。セットがソートされている場合、バイナリ検索で mlog(m)N を取得したり、ソートされたケースで 2 つのイテレータを進めることで O(mN) を取得したりできます。

于 2013-03-07T06:37:26.030 に答える
2

セットの要素をハッシュできること、および辞書のようなハッシュ キー機能があること (または、独自に作成できることは難しくありません) を仮定します。

List<Set<element-type>> sets;    \\your list of sets to intersect

int size = SUM{List[*].Count};  \\ size for the hash
Dictionary<element-type,int> Tally = New Dictionary<element-type,int>(size);

// Add all elements to the Tally hash
foreach set in sets
{
    foreach e in set
    {
        if (Tally.Exists(e))
            Tally[e]++;
        else
            Tally.Add(e,1);
    }
}

//Now, find the Tally entries that match the number of sets
foreach kvp in Tally.KeyValuePairs
{
    If (kvp.Value == sets.Count)
        // add the Key to output list/set
        Output.Add(kvp.Key);
}

これには、実行時の複雑さが O(n) あります。「n」は、すべてのセットの要素の数です。

于 2013-03-07T14:06:43.453 に答える
1

今のところ、セットはリストとして表され、最初はソートされていないと仮定します。

(私のシンボルを @perreal のシンボルに適合させるために編集されました)

N 個のセットに合計 m*N 個のアイテムがある場合、セットを単一のリストに連結し (m*N 操作)、リストを並べ替え (m*N log m*N 操作)、並べ替えられたリストを実行できます。正確にN個のコピー（別のm * N操作）を持つリスト内のアイテムを保持し、すべてのケースで合計（私が思うに）m * N（2 + log m * N）操作を与えます。

比較すると、各セットに同じ数のアイテム m があると仮定すると、セットがすべて同一である場合、@perreal のソリューションは最大 m^2*N 操作になると思います。これには、m*N の大きな値に対して、私のアルゴリズムの m*N (2 + log m*N) 操作よりも多くの操作が必要になります。ただし、最良の場合、@perreal のソリューションは 2m*N 操作しか必要としません (テストされた最初と 2 番目のセットに交差がない場合)。

@perreal のソリューションでは、S_1 が最小のセットであるサイズの昇順でセットを比較すると、交差が小さい場合に必要な操作も少なくなります。

セットが並べ替えられたリストとして開始された場合、私のアルゴリズムの最初の並べ替えが不要になり、@perreal のアルゴリズムがセット全体を検索することなく要素がセットに含まれていないと判断できるため、両方のソリューションが高速になります。

于 2013-03-07T07:00:44.647 に答える