Union-Find의 시간복잡도

Union-Find를 구현하는 방식에는 두 가지가 있다.

첫 번째는 linked list를 활용하여 구현하는 방식이고, 두 번째 방식은 우리가 일반적으로 알고 있는, Tree를 사용해서 구현하는 방식이다. 각각에 대하여 시간복잡도가 다르기 때문에 두 경우로 나누어서 분석해보겠다.

 

모든 경우에 대해서 총 m개의 연산 (make, find, union)이 가능하고, make-set의 개수 (=원소의 개수)는 n개라고 가정하에 시간복잡도를 계산해보겠다.

---

1. Linked List를 활용하는 경우 : O(m+ nlogn)

 

이 경우에는 시간복잡도가 O(m +nlogn)이라고 알려져있다. 직관적으로 설명한다면 linked list의 경우 길이가 짧은 linked list를 길이가 긴 linked list에 붙이는 것이기 때문에 union 현산 시에 내가 속한 집합의 크기가 최소 2배 이상 커진다. 따라서 update가 될 수 있는 횟수는 최대 logn 번이며, 각 union 연산시마다 O(n)만큼의 시간복잡도가 소요되기 때문에 

O(m + nlogn)이라고 할 수 있다. 여기서 m은 make-set과 find-set처럼 상수시간이 걸리는 overhead를 더해 준 것이다. 

 

따라서 이 경우에 m 이 n에 가까운 숫자의 경우에는 O(nlogn)의 시간복잡도를 가질 것이지만 m이 커지게 된다면 O(m) 시간복잡도를 가지게 될 것이다.

 

2. Tree를 이용하는 경우 (Union by rank와 Path compression (경로압축)을 사용하는 경우) 

 

여기서 경로압축을 사용하는 방식은 

2021.03.13 - [CS 일반] - [유니온 파인드] union find 경로 압축

[유니온 파인드] union find 경로 압축

위 포스팅에서 다루었으니 익숙하지 않으면 위 포스팅을 확인해보자.

 

이 경우에 시간복잡도는 많은 연구자들에 의해 논문에서 증명이 되었고 점차 tight한 시간복잡도로 시간복잡도가 계속 update되었다.

 

먼저 Fischer에 의해 O(mloglogn)이라는 것이 증명되었고

Hopcroft and Ullman에 의해 O(mlog*n)의 시간복잡도라는 것이 증명되었다.

 

여기서 log*n은 min{ k : loglog ....log n<=1} 즉, 숫자가 1 이하가 될때까지 시행한 log의 횟수를 뜻한다.

 

여기서 나아가 Tarjan이라는 사람은 θ(mα(n))이라는것을 증명해냈다. 여기서 α는inverse Ackermann function을 뜻한다.

 

즉, Union-Find의 시간복잡도는 여러 사람들에 의해 증명되었고 어떤 방식으로 구현하는지에 따라 시간복잡도가 달라질 수 있다.