여러 세트의 교차점에 대한 알고리즘 모델

Question

제 질문은 어떻게 5 ~ 7 세트의 교차점을 적용 할 수 있습니까? 각 세트가 요소 세트를 가지고 있다고 가정하십시오. 이를위한 알고리즘을 만드는 데 도움이되고이 과정의 복잡성은 무엇입니까?

Answer 1

정직있어서, 각각의 세트는 m 요소를 갖고 N 세트가있는 경우,이 복잡성

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 개의 ^이다. 세트가 정렬되면 정렬 된 케이스에서 두 개의 반복자를 사용하여 mlog (m) N (바이너리 검색 또는 O (mN))을 가질 수 있습니다.

Answer 2

나는 그 세트가리스트로 표현되고 그것이 정렬되지 않은 것으로 시작한다고 가정 할 것이다.

종류, 하나는 하나의리스트로 세트 (m의 *의 N 작업)을 연결할 수

는 N 세트에서 m의 *의 N 항목의 총을 감안할 때 (@perreal의 사람들에게 내 심볼을 준수하도록 수정 됨) 리스트 (m * N log m * N 연산)를 수행 한 다음 정렬 된 목록을 실행하여 목록에 정확히 N 개의 사본 (다른 m * N 작업)이있는 항목을 유지하고 m * N (2 + logm * N) 연산을 수행합니다.

비교하면 각 세트가 같은 수의 항목 m을 가지고 있다고 가정 할 때 집합이 모두 동일하면 @ perreal의 솔루션은 최대^2 * N 작업이 될 것이라고 생각합니다. 그것은 m * N의 큰 값에 대해 내 알고리즘의 m * N (2 + log m * N) 연산 이상을 요구합니다. 그러나, 가장 좋은 경우, @ perreal의 솔루션은 2m * N 작업을 필요로합니다 (테스트 된 첫 번째와 두 번째 세트에는 교차가없는 경우).

@ perreal의 솔루션은 또한 세트가 크기 순서대로 비교되는 경우 교차가 작은 경우에 더 적은 연산이 필요합니다. S_1이 가장 작은 세트입니다.

세트가 정렬 목록으로 시작된 경우 내 알고리즘의 초기 정렬이 필요하지 않으므로 두 가지 솔루션 모두 빠를 것입니다. @ perreal의 알고리즘은 검색 할 필요없이 요소가 세트에 없다는 것을 결정할 수 있습니다 전체 세트.

Answer 3

세트의 요소가 해시 될 수 있다고 가정하면, 당신은 사전과 같은 몇 가지 해시 - 주요 시설이 (또는 하드하지 않은, 자신의 당신을 만들 수) 있음 :

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"은 모든 세트의 요소 수입니다.