n번 merge하는데 최악의 경우엔 O(n^2)일 수도 있지 않을까 해서요.

두 집합을 set merge할 때 size가 큰쪽에 작은 것을 넣는 식으로만 합쳐진다고 하면 O(n * log(n))일 것 같은데.. 

점화식으로 구할 수 있을 것 같긴 한데..

f[n] = max( f[m] + f[n-m] + min(m, n-m) ), 1<=m<n

f[1] = 0

이걸 어떻게 풀까요..

f 는 O(n log n)이 맞을까요? 

두 집합이 합쳐진다면 작은 쪽의 집합이 큰 집합 쪽으로 이동하게 되고, 이동하는 쪽의(작은) 집합을 기준으로 보면 크기가 2배 이상 증가하게 됩니다.

즉, 각 원소가 이동을 할 때마다 속한 집합의 크기가 2배 이상 증가하므로 아무리 많이 이동해봤자 logN번 이동할 수 있습니다.

모든 원소에 대해서 이동하는 횟수를 보면 총 시간복잡도는 O(NlogN) 입니다.

초기상태: {1}, {2}, {3}, {4}, {5}, ..., {n}  비용 0

다음상태: {1, 2}, {3}, {4}, {5}, ..., {n}.    비용 1

...

최종상태: {1, 2, 3, 4, 5, ..., n}             비용 x

이렇게 했을 때 x는 O(n log n)인거죠??

크기가 2배씩 증가하면 log n번인 것은 {1}, {2}, {3, 4}, {5, 6, 7, 8}, ... 이면 인건가요??

아하 이해했.. 음.. 아하..!!!

각 원소별로 log n번 이동하면 n log n인거군요

set쓰니까 n (log n)^2 이 되려나요.

이해했습니다. 감사합니다.

Disjoint set 구현을 skewed되지않게 잘 해야겠네여..

https://en.wikipedia.org/wiki/...

Disjoint Set Forest에서 Union구현할 때

Union by size으로 cardinality가 작은 set을 큰 set으로 붙여주는 방법,

Union by rank으로 tree height upper bound가 작은 set을 큰 set으로 붙여주는 방법

이런 두가지 방법이 있는지 처음알았습니다.

이 문제에서는 union by size로 구현해야 좋겠..?? 모르겠습니다.

size 든 rank든 결국 root로 가는 간선의 개수는 최대 log N개 이므로 둘 다 시간복잡도는 만족할 거 같습니다.

하지만 size로 하게되면 set의 크기만 비교하면 쉽게 구현 할 수 있어 보통 small to large는 union by size로 구현합니다.