노조 찾기 구조는 다음의 동작을 지원하는 데이터 구조 인 y)는 x 및 y가 포함 된 집합을 단일 집합으로 병합합니다.끊긴 세트 연합 데이터 구조
찾기 (x)는 우리가 계급의 사용 개념을 advisied되는 O는 (n)이, 그래서이 문제를 개선하기 위해 의 시간 복잡도를 가지고있다
즉 큰 연결된 기기는 작은 먹는다 O (logn) 나는
을 우리가 순위 (깊이) 자신의 기본에 나무를 병합하여 시간 복잡성을 개선하고 어떻게 이해하고 어떻게 O 수없는 시간의 복잡성을 향상
일 (logn) 시간 복잡도가 달성됩니다.
나무의 병합 개념에 대한 이해를 도와주세요.
집합을 나타내는 트리의 최대 높이가 크기 log(n) + 1임을 이해하는 것이 중요하므로 주어진 노드에서 그 루트까지의 노드를 따라 가면 O(log(n)) 단계가됩니다.
이제 disjoint set 포리스트의 각 트리가 높이 log(n) + 1 -이 트리의 노드 수인 n 인 것을 증명해야합니다. 우리는 유도에 의해 그것을 입증 할 것이고, 각각 union(x,y) 이후에 -이 자산은 변하지 않은 것을 보여줄 것입니다.
자료 : - : 우리는 두 가지를 결합 우리가 시작할 때, 우리는 n 다른 나무, 크기 1 log(1) + 1 = 1의 모든이가 각각의 나무는 참으로 최대 높이의 log(n) + 1
연합 (x, y)에입니다 세트 x은 n1이고, 사이즈는 n2이다. 보편성을 잃지 않고 n1<=n2으로 지정하십시오. 유도 가설에서
이 x를 나타내는 트리의 높이 (H1) 그래서 대부분의 log(n2)+1 이며, 노조 작업은의 루트 'y를 가리 키도록의 루트'x을 변경하여 수행됩니다. 이것은 x에 있던 모든 노드의 최대 높이가 지금에서 가장
x에 공식적으로 있었다 모든 노드에 대해 루트 최대 거리가
log(n1+n2) + 1 것을 발견했다
h1+1 = log(n1)+1 + 1 = log(n1) + log(2) + 1 = log(2*n1) + 1 = log(n1 + n1) + 1 <= log(n1 + n2) + 1
것을 의미 새 트리 (x 및 y)의 크기가 이제 n1+n2이되므로 형식적으로 x 인 모든 노드에 대해 원하는 속성이 남아 있음이 입증되었습니다. y의 경우 - 루트까지의 거리는 유지되지만 트리의 크기는 축소되지 않으므로 속성도 유효합니다.
결론 - x 또는 y에있는 모든 노드에 대해 새 루트의 최대 깊이는 필요에 따라 log(n1+n2)+1입니다.
QED
말 -이 답변의 모든 log은베이스 2.