불연속 집합 찾기 및 결합 연산의 복잡성

Question

불연속 집합에 대한 알고리즘을 연구 중입니다.

그리고 Fast FIND Implementation (Quick Find)

데이터 구조의 제는 다음과 같다 : 예

) 실시 예 상술 [number] = set name에서

int array[5] 

[0] = 3, 
[1] = 5, 
[2] = 7, 
[3] = 1, 
[4] = 2, 

(), 숫자 세트 이름의 원소이다.

그래서, 숫자 0 등 번호 1 세트 5, ...로하고, 세트 3에

연합 (a, b) (a가 세트 I 및 B는 것을 가정 수행 집합 j에 있음), O (n) 연산이 필요합니다. 나는이 사실을 알고. 그 이유는 다음과 같습니다 (의사 코드) : 책에

void Union(a, b) { 
     int set1 = Find(a); /* set 1 will be 'i' */ 
     int set2 = Find(b); /* set 2 will be 'j' */ 

     if(set 1 != set2) 
      for(int i = 0; i < sizeof(array); i++) { /* O(n) operation */ 
       if(array[i] == set1) 
        array[i] = set2; 
      } 
} 

그러나, 나는 이것을 이해할 수 없다 :

이

N의 순서 - 1 개 노조 (N^2) 시간이 O를 가지고 최악의 경우. O (n^2) FIND 연산이있는 경우 각 UNION 또는 FIND 연산에 대한 평균 시간 복잡도가 O (1)이므로이 성능이 좋습니다. FIND가 적 으면이 복잡성이 허용되지 않습니다.

나는이 문장의 의미가 무엇이고 왜 복잡성이 O (n^2)인지 이해할 수 없다. 위에서 작성한 코드처럼이 복잡성을 상상할 수는 없습니다.

Answer 1

모든 작업의 ​​복잡성을 가능한 한 최소화하고자합니다.

총 복잡성 = 복잡성 (FIND) + 복잡성 (UNION)

우리는 N의 순서 주어진 경우에 당신이 언급 한 바와 같이 - (1) 노동 조합은 최악의 경우 (N^2) 시간 O을. 그리고 find는 평균적으로 O (1)을 취합니다.

n-1 조합 연산의 경우 O (n^2)보다 큰 전체 복잡도를 증가시키지 않으면 얼마나 많은 find를 얻을 수 있습니까?

대답은 O (n^2) 찾기 작업을 지원할 수 있습니다.

그래서 긴 FIND 수가 < = O (N^2)과 UNION의 개수로 < = O (N)이다. 복잡성은 동일합니다.

일반 규칙 : 무거운 작업 (더 많은 시간이 소요)은 더 가벼운 작업의 무게만큼 적은 횟수로 사용되어야하고 더 가벼운 작업은 무거운 작업의 무게만큼 많은 횟수로 사용해야합니다.

이 정도면 충분합니다.