Small To Large 내가 이해한 대로 설명하기

오랜만에 글을 올려봅니다.

"DSU 알고리즘에서 크기를 기준으로 union을 하면 O(NlogN)이 된다." 이게 Small-to-Large technique으로 전 알고 있습니다.

다만 이게 왜 O(NlogN)인가는 좀 직관적으로 이해가 잘 안 갔었는데... 최근에 인사이트가 생겨 이를 공유해보고자 합니다.

 

자... DSU 알고리즘에서 모든 element를 Union을 할 때 생기는 시간복잡도는 "모든 element가 이동한 횟수"가 될 것입니다.

그러면 각 element가 몇 번 정도 움직이는 지 파악하면 되겠죠?

 

그러면 각 element가 언제까지 움직여야 할까요?

조금 비틀어서 생각해보면 현재 element가 속한 집합의 크기가 N이 될 때 까지가 됩니다.

 

현재 element a가 속한 집합의 크기가 sz[a]라고 합시다. 

그리고 집합의 크기가 sz[b]인 집합과 union해야 하는 상황이라고 보죠.

 

만약에 sz[a] > sz[b]라면 sz[a] := sz[a]+sz[b]가 되긴 합니다. 다만, element a는 움직이지 않죠.

그러나 sz[a] < sz[b]라면 sz[b] := sz[a]+sz[b]가 되고 element a는 움직이게 됩니다.

그러면 element a가 속한 집합은 크기가 sz[a]에서 sz[a] + sz[b] > 2 * sz[a]가 됩니다.

적어도 element a 가 속한 집합의 크기가 2배 이상이 되는 경우에 element a가 움직이게 되는거죠!

 

그러면 element a는 최대 몇 번을 움직이는 걸까요?

한 번 움직일 때 적어도 element a가 속한 집합의 크기 sz[a]는 sz[a] * 2 이상이 됩니다. 

그러면 총 움직이는 횟수는 대략... sz[a] * 2 ^ (움직인 횟수)  = N 이므로 움직인 횟수 > logN 정도 되겠네요.

 

따라서  각 element는 O(logN) 정도 움직이게 됩니다.

그러면 총 element가 움직인 횟수는 O(NlogN)이 되겠죠. 

그래서 Small-to-Large Technique이 O(NlogN)이 되는 겁니다.

 

누군가에겐 이게 매우 당연할 수 있긴 할텐데...

저는 이걸 처음 본 걸 기준으로 대략 2년 정도 지나서야 직관적으로 이해되었습니다.

그래서 이걸 제가 이해한 대로 나름 풀어서 공유해보고자 적었습니다.

 

이 글이 도움되셨다면 좋겠습니다!