imeimi / Algorithm DB

Path Compression + Union by Rank

1정의

경로 압축과 랭크 기반 합치기를 함께 적용하는 기법이다.

2구현

int parent[N], rnk[N];

void init(int n) {
    for (int i = 0; i < n; i++) parent[i] = i, rnk[i] = 0;
}

int find(int x) {
    if (parent[x] == x) return x;
    return parent[x] = find(parent[x]);
}

void unite(int x, int y) {
    x = find(x); y = find(y);
    if (x == y) return;
    if (rnk[x] < rnk[y]) swap(x, y);
    parent[y] = x;
    if (rnk[x] == rnk[y]) rnk[x]++;
}

3시간 복잡도

n개의 원소에 대해 m번의 연산을 수행하는 총 시간 복잡도는 O(m · α(n))이다.

α(n)은 역아커만 함수(inverse Ackermann function)다.

4증명

4.1아커만 함수와 역아커만 함수

함수 Ak(j)를 다음과 같이 정의한다 (k ≥ 0, j ≥ 1).

  • Ak(j) = j + 1 (k = 0)
  • Ak(j) = Ak−1(j+1)(j) (k ≥ 1)

여기서 f(i)는 f를 i번 반복 적용한 합성 함수다. f(0)(j) = j, f(i)(j) = f(f(i−1)(j)).

  • A1(j) = A0(j+1)(j) = j + (j+1) = 2j + 1
  • A2(j) = A1(j+1)(j) = 2j+1(j+1) − 1
  • A3(1) = A2(2)(1) = A2(A2(1)) = A2(3) = 2047

역아커만 함수 α(n) = min{k : Ak(1) ≥ n}으로 정의한다. n ≤ 2A3(1) = 22047이면 α(n) ≤ 4다.

4.2level과 iter 정의

루트가 아닌 노드 x에 대해, rnk(x) ≥ 1이면 다음을 정의한다.

level(x) = max{k : Ak(rnk(x)) ≤ rnk(parent(x))}

iter(x) = max{i ≥ 1 : Alevel(x)(i)(rnk(x)) ≤ rnk(parent(x))}

rnk(x) = 0이거나 x가 루트이면 정의하지 않는다.

4.3보조 정리 1

루트가 아니고 rnk(x) ≥ 1인 노드 x에 대해 다음이 성립한다.

  • 0 ≤ level(x) ≤ α(n) − 1
  • 1 ≤ iter(x) ≤ rnk(x)

Aα(n)(1) ≥ n이고 n > rnk(parent(x))이므로 Aα(n)(rnk(x)) ≥ Aα(n)(1) ≥ n > rnk(parent(x))다. 따라서 level(x) ≤ α(n) − 1이다.

level(x) = k라 하면 정의에 의해 Ak(rnk(x)) ≤ rnk(parent(x)) < Ak+1(rnk(x))이다. Ak+1(rnk(x)) = Ak(rnk(x)+1)(rnk(x))이므로 Ak(rnk(x)+1)(rnk(x)) > rnk(parent(x))이다. 따라서 iter(x) ≤ rnk(x)다. ■

4.4포텐셜 함수

노드 x의 포텐셜 φ(x)를 다음과 같이 정의한다.

  • φ(x) = α(n) · rnk(x) (x가 루트이거나 rnk(x) = 0)
  • φ(x) = (α(n) − level(x)) · rnk(x) − iter(x) (그 외)

전체 포텐셜 Φ = ∑x φ(x)다.

4.5보조 정리 2

모든 노드 x에 대해 0 ≤ φ(x) ≤ α(n) · rnk(x)이다.

x가 루트이거나 rnk(x) = 0일 때는 자명하다.

그 외의 경우, level(x) ≤ α(n) − 1이므로 α(n) − level(x) ≥ 1이다. 따라서

φ(x) = (α(n) − level(x)) · rnk(x) − iter(x) ≥ 1 · rnk(x) − rnk(x) = 0

이다. 또한 iter(x) ≥ 1이므로 φ(x) ≤ (α(n) − level(x)) · rnk(x) ≤ α(n) · rnk(x)이다. ■

보조 정리 2에 의해 초기 상태에서 Φ = 0이고, Φ ≥ 0이 항상 성립한다.

4.6unite의 분할 상환 비용

rnk(x) ≥ rnk(y)일 때 y가 x의 자식이 되었다고 하자.

  • rnk(x) = rnk(y)이면 rnk(x)가 1 증가하므로 Δφ(x) = α(n). rnk(x) > rnk(y)이면 rnk(x)는 변하지 않으므로 Δφ(x) = 0.
  • y는 루트에서 비루트가 된다. 보조 정리 2에 의해 새 φ(y) ≤ α(n) · rnk(y) = 이전 φ(y)이므로 Δφ(y) ≤ 0.
  • 다른 노드의 포텐셜은 변하지 않는다.

따라서 ΔΦ ≤ α(n)이다. 실제 비용 O(1)을 더하면 unite의 분할 상환 비용은 O(α(n))이다.

4.7find의 분할 상환 비용

find가 경로 v1, v2, ⋯, vl = r을 탐색한다고 하자. 실제 비용은 l − 1이다. 경로 압축 후 v1, ⋯, vl−1의 부모가 모두 r로 바뀐다.

인접 쌍 (vi, vi+1)을 세 유형으로 분류하여 분할 상환 비용 â = 실제 비용 + ΔΦ를 계산한다.

4.7.1유형 1: rnk(vi) = 0 또는 vi = vl-1

rnk는 경로를 따라 순증가하므로 rnk(vi) = 0은 i = 1일 때만 가능하다. vl-1은 루트의 직전 노드로 하나뿐이다. 따라서 유형 1은 최대 2쌍이다.

압축 후 v1의 rnk는 0으로 불변이고, vl-1의 부모는 이미 r이므로 두 경우 모두 Δφ = 0이다. 따라서 â1 = 1이다.

4.7.2유형 2: 경로 상에 j > i이고 level(vj) = level(vi)인 j가 존재

level(r)은 정의되지 않으므로 j < l이다. level(vi) = k, iter(vi)의 이전/이후 값을 iterold, iternew라 하자.

iter의 정의에 의해 Ak(iterold)(rnk(vi)) ≤ rnk(vi+1) ≤ rnk(vj)이고, level의 정의에 의해 Ak(rnk(vj)) ≤ rnk(vj+1) ≤ rnk(r)이다. 이를 합치면 Ak(iterold+1)(rnk(vi)) ≤ rnk(r)이다.

φ(vi) = (α(n) − level(vi)) · rnk(vi) − iter(vi)이므로 Δφ(vi) = −Δlevel(vi) · rnk(vi) − Δiter(vi).

  • Δlevel(vi) = 0이면 Δiter(vi) ≥ 1이므로 Δφ(vi) ≤ −1이다.
  • Δlevel(vi) ≥ 1이면 Δlevel(vi) · rnk(vi) ≥ rnk(vi)이고, Δiter(vi) ≥ 1 − rnk(vi) (iternew ≥ 1, iterold ≤ rnk(vi))이므로 Δφ(vi) ≤ −rnk(vi) − (1 − rnk(vi)) = −1이다.

따라서 ΔΦ ≤ −1이므로 â2 ≤ 1 − 1 = 0이다.

4.7.3유형 3: 그 외

유형 1, 2에 해당하지 않는 쌍이다. 이 경우 경로 상에서 level(vi)와 같은 level을 가진 후속 노드가 없다. level은 {0, ⋯, α(n) − 1}에 속하므로 유형 3은 최대 α(n)쌍이다.

iter(vi)의 이전/이후 값을 iterold, iternew라 하자.

φ(vi) = (α(n) − level(vi)) · rnk(vi) − iter(vi)이므로 Δφ(vi) = −Δlevel(vi) · rnk(vi) − Δiter(vi).

  • Δlevel(vi) = 0이면 Δiter(vi) ≥ 0이므로 Δφ(vi) ≤ 0이다.
  • Δlevel(vi) ≥ 1이면 Δlevel(vi) · rnk(vi) ≥ rnk(vi)이고, Δiter(vi) ≥ 1 − rnk(vi) (iternew ≥ 1, iterold ≤ rnk(vi))이므로 Δφ(vi) ≤ −rnk(vi) − (1 − rnk(vi)) = −1 < 0이다.

두 경우 모두 Δφ(vi) ≤ 0이므로 â3 ≤ 1이다.

4.7.4결론

â = ∑ â1 + ∑ â2 + ∑ â3 ≤ 2 + 0 + α(n) = O(α(n)).

따라서 m번의 연산에 걸친 전체 시간 복잡도는 O(m · α(n)) 이다. ■

5하한

이 문제의 분할 상환 하한은 Ω(α(n))이다. O(α(n))은 점근적으로 최적이다.

6참고 문헌

  • Tarjan, R. E. (1975). Efficiency of a good but not linear set union algorithm. Journal of the ACM, 22(2), 215–225.
  • Fredman, M. L., & Saks, M. E. (1989). The cell probe complexity of dynamic data structures. Proceedings of the 21st Annual ACM Symposium on Theory of Computing, 345–354.
  • Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.), Chapter 21. MIT Press.