0

私はたくさんのセット、A1、A2、A3、... AN を持っています。各セットには、0 から 2000 までの値の N 要素 (最大 1000 としましょう) が含まれます。

A1{1,2,3,4}
A2{2,4,3,5}
A3(1,2,5,6)

サイズ k、たとえば 3 の場合、A1 の組み合わせは C1(1,2,3)、C2(1,2,4)、C3(2,3,4) になります。 A1 のすべての組み合わせが、A2 から AN までの組み合わせのどこかに存在する場合。

つまり、A1 の組み合わせ C3 は、A2 の組み合わせと一致し、場合によっては AN と一致します。ここで、A2 から AN に対する A1 の C1 と C2 の結果が必要です。単純で効率の悪い方法は、すべての集合 A1 から AN に対して k サイズのすべての組み合わせを生成することです。次に、A の C1 に対して、A2 から AN に存在する場合。次にC2、C3。その後、次のセットに進み、繰り返します。

新しいセットが追加されると、頻繁で高価な計算が必要になるため、この方法をどのように改善できますか?

私が見つけたもう 1 つの解決策は、最適化せずに O(N^2 + N) で実行されます。これには、基本的に A1 と A2...AN の交点を取り、それらの交点の組み合わせを計算し、それらの各組み合わせの回数を確認することが含まれます。生成された結果に発生します。

4

1 に答える 1

0

組み合わせをハッシュ化してみることができます。ここでは、スペースを最適化するアプローチと時間を最適化するアプローチの 2 つのアプローチを使用できます。時間を最適化するために、ハッシュ関数は組み合わせごとに一意のキーを作成し、すでに占有されている場所でヒットすると、その組み合わせに遭遇するのは初めてではないことがわかります。スペースの最適化の方法は似ていますが、キーは一意ではありません。キーに対応する組み合わせのリストを管理し、ヒット時にそれをトラバースして、現在チェックしている組み合わせが含まれているかどうかを確認する必要があります。キーの一意性の程度によって、テーブルのサイズが決まり、その結果、ヒットの検証に費やす必要がある時間が決まります。

于 2012-11-03T06:14:45.520 に答える