세트 처리
- Mutually Exclusive Sets: 공통 요소가 없는 요소, 즉 상호 배타적인 하위 집합으로 나누어지는 요소에 대한 정보를 저장하고 조작하기 위한 데이터 구조입니다.
- 교차로 없음
- 뮤텍스를 처리하려면 연결된 목록 또는 트리를 구현하여 추상화하십시오.
- 운영 지원
- make-set(x): 요소 x만 포함하는 집합을 생성합니다.
- find-set(x): 요소 x를 포함하는 집합을 찾습니다.
- union(x,y) : 요소 x를 포함하는 집합과 요소 y를 포함하는 집합의 합집합
- make-set(x): 요소 x만 포함하는 집합을 생성합니다.
연결된 목록을 사용하여 처리 설정
- 동일한 컬렉션의 요소는 연결 목록으로 관리됩니다.
- 연결된 목록의 첫 번째 요소는 집합의 대표 요소로 사용됩니다.
무게 공동 고려
- 두 세트의 연결 목록을 결합할 때 더 작은 세트가 더 큰 세트에 추가됩니다.
- 이는 대표 요소에 대한 포인터 업데이트 작업을 최소화하기 위한 것입니다.
- m개의 make-set, union, find-set 중 n개가 make-set이면 총 실행 시간은 O(m+nlogn)입니다.
→ make-set과 find-set은 일정한 시간 O(m)만 걸린다.
결합에 걸리는 시간은 요소당 logn이고 n개 요소에 적용될 때 O(nlogn)입니다.
트리를 사용한 컬렉션 작업
- 동일한 컬렉션의 요소는 트리로 관리됩니다.
- 부모 노드를 가리키는 자식 노드
- 트리의 루트는 컬렉션의 대표 요소 역할을 합니다.
make_set(x) //노드 x를 유일한 원소로 하는 집합을 만든다.
{
p(x) <- x;
}
union(x,y) //노드x가 속한 집합과 노드 y가 속한 집합을 합친다.
{
p(Find_set(y)) <- find_set(x);
}
find_set (x)
{
if(x=p(x))
then return x;
else return Find-Set(p(x));
}
겸용 등급
- 각 노드는 해당 노드를 기반으로 하는 하위 트리의 높이를 결정합니다.
계급다른 이름으로 저장 - 두 세트를 결합할 때 낮은 등급의 세트가 높은 등급의 세트에 추가됩니다.
make_set(x){
p(x) <- x;
rank(x) <- 0;
}
union(x,y){
x'<-Find_set(x);
y'<-Find_set(y);
if(rank(x')> rank(y'))
then p(y') <- x';
if (rank(x`) = rank(y`)) then rank(y`) <- rank(y`)+1;
}
경로 압축
- 찾기 세트를 실행하는 과정에서 마주치는 모든 노드는 포인터를 변경하고 직접 루트를 가리킵니다.
find_set(x){
if(p(x) !
= x) then p(x) <- find_set(p(x));
return p(x);
}
능률
- 순위 조합 사용
- 더 이상 성적이 나오지 않는 방향으로 결합
- 랭크 k 집합에는 적어도 2^k 요소가 있어야 합니다.
- 요소의 수가 n이면 순위는 O(log n)입니다.
- 경로 압축
- 낮은 순위.
- m개의 make-sets, unions, find-sets의 실행 시간은 m개의 make-sets 중 n개가 make-sets일 때 트리로 표현되는 배타적 집합에서 rank-used union을 사용하는 경우 O(mlogn)입니다.
- 요소의 수는 n이고, find-set은 순위에 따라 다르며, 임의 노드의 순위는 O(logn)입니다.
- 요소의 수는 n이고, find-set은 순위에 따라 다르며, 임의 노드의 순위는 O(logn)입니다.
- 트리로 표현되는 배타적 집합에서 순위를 이용한 합집합과 경로 압축을 이용한 찾기 집합을 모두 사용하면 m개 메이크셋, 유니온, 찾기셋 중 n개가 메이크셋일 때 실행 시간이 줄어든다.
O(mlog*n)입니다.
n에 k번 log를 적용했을 때 처음으로 k가 1보다 작아지는 시점을 나타냅니다.
이것은 매우 작은 사실상의 상수로 볼 수 있습니다.
따라서 정리는 최악의 경우 O(m) 시간이 걸린다고 말합니다.