Path Comprssion DSU의 amortized O(logN) 증명

Weighted union rule, Path compression 중 하나만 사용하면 amotized \(O(logN)\), 둘 모두를 사용하면

amortized \(O(\alpha(N))\)임이 잘 알려져있습니다.

Path compression만을 사용했을 때 시간복잡도의 증명은 한글 자료가 잘 없는 것 같아 작성합니다.

 

Heavy Light Decomposition스러운 논리를 사용합니다.

정점 u가 v의 자식일 때 sz[v] \(\leq\) sz[u] / 2이면 u->v간선은 light edge, 나머지는 heavy edge라고 해봅시다. 

당연하게도 heavy edge는 정점당 하나만 생깁니다

(sz[x] := x의 서브트리의 크기)

 

임의의 정점 (u, v)에 대해 u->v로 가는 경로는 최대 \( O(logN) \)개의 light edge를 거칩니다.

light edge를 거치게 되면 고려할 정점이 적어도 1/2씩 줄어들기 때문에 \( O(logN) \)임을 단정지을 수 있어요.

경로에 heavy edge가 몇개나 있을지는 생각하지 않고 일단 a라고 두겠습니다.

 

int find(int a) {
	if(a == pa[a]) return a;
	else return pa[a] = find(pa[a]);
}

 

위처럼 구현된 find(a)의 코스트는 (루트까지 가는 간선의 개수) = (heavy edge의 개수 + light edge의 개수) \(\in O(a + logN)\)이 되겠져

 

find에서 한번 거친 heavy edge u->v가 어떻게 될지 생각해보면 결국 Path compression에 의해 해당 heavy edge는 사라지고

루트 아래에 루트->i의 light edge가 sz[u]개 생기겠죠. 그래서 결국 쿼리를 몇번 수행하던 \(\sum{a} \in O(\)merge의 개수\() \subset O(M)\)입니다. 

* light edge가 늘어나던 말던 결국 트리의 형태이기 때문에 어떤 경로던 light edge를 최대 \(O(logN)\)개 거친다는 것은 변하지 않습니다.

 

따라서 N개의 정점에 M번 쿼리를 수행하게 된다면 총 \(O(M+MlogN)\)번의 연산을 수행하게 되고 

DSU의 연산이 amortized \(O(logN)\)임을 알 수 있습니다.

 

+ path halving 구현일때도 거의 같은 논리로 보일 수 있습니다.

pa[pa[a]]->pa[a]->a에서 두 간선 중 하나 이상이 light edge인 경우는 \(O(logN)\)이니 경로에서

이 경우는 \(O(logN)\)개이고 pa[a]->a가 heavy edge인 경우도 똑같이 한번 find를 거치면 light edge로 바뀝니다.

둘다 heavy edge인 경우는 한번 거치면 heavy edge 하나 + light edge로 바뀝니다.

따라서 똑같이 amortized \(O(logN)\)입니다.

path halving이 일반적으로 더 빠르다는데 이건 경험적으로만 알 수 있는 것 같습니다.. 

 

int find(int a) {
	while(a != pa[a]) {
		pa[a] = pa[pa[a]];
		a = pa[a];
	}
	return a;
}

 

아아.. 로버트 타잔 또 당신입니까?