복잡도: 역 아커만 함수를 쉬운 말로

유니온 파인드는 "거의 상수 시간"이라는 말로 자주 소개됩니다. 이 장에서는 그 말이 정확히 무엇을 뜻하는지, 최적화를 하나씩 더할 때 비용이 어떻게 줄어드는지, 다른 방법과 비교하면 어떤지 정리합니다.

최적화별 비용

n은 원소 수, m은 find와 union 호출 횟수입니다. union은 내부에서 find를 두 번 부르므로 비용이 find와 같은 수준입니다.

마지막 줄의 α(n)이 역 아커만(inverse Ackermann) 함수입니다.

역 아커만 함수란

아커만 함수는 입력이 조금만 커져도 값이 상상할 수 없을 만큼 빠르게 커지는 함수입니다. 역 아커만 함수 α(n)은 그 반대로, "아커만 함수 값이 n에 닿으려면 입력이 얼마나 커야 하는가"를 묻습니다. 아커만 함수가 터무니없이 빨리 자라므로 α(n)은 터무니없이 느리게 자랍니다.

쉬운 말로 하면, 우주에 있는 원자 수보다 훨씬 많은 원소를 다루더라도 α(n)은 4를 넘지 않습니다. 그래서 m번 연산의 총비용 O(m α(n))은 실제로는 "연산 한 번에 작은 상수"라고 읽어도 됩니다. 다만 이론적으로는 상수가 아니며, Tarjan은 이 상한이 포인터 기반 구조에서 더 줄일 수 없는 하한이기도 하다는 것을 보였습니다.

비교를 위해 로그 함수와 나란히 보면 차이가 분명합니다.

분할 상환(amortized)이라는 뜻

경로 압축이 있으면 어떤 find 한 번은 길게 걸릴 수 있습니다. 그러나 그 find가 지나간 경로를 납작하게 만들어 두므로 이후 호출이 빨라집니다. 그래서 개별 호출이 아니라 m번 전체의 합으로 비용을 따지며, 이를 분할 상환 분석이라고 합니다. 실시간 시스템처럼 호출 한 번의 최악 시간이 중요하다면 이 점을 염두에 둬야 합니다.

직접 확인하기

아래 코드는 최적화 없이 한 줄로 길어진 트리와 두 최적화를 모두 쓴 트리에서 가장 깊은 노드의 깊이를 비교합니다.

def depth(parent, x):
    d = 0
    while parent[x] != x:
        x = parent[x]
        d += 1
    return d

n = 1 << 12
naive = list(range(n))
for i in range(1, n):
    naive[i - 1] = i            # 앞 루트를 뒤 원소 밑에 붙이기
print(max(depth(naive, x) for x in range(n)))   # 4095

parent, size = list(range(n)), [1] * n
def find(x):
    while parent[x] != x:
        parent[x] = parent[parent[x]]
        x = parent[x]
    return x
for i in range(1, n):
    ra, rb = find(i - 1), find(i)
    if size[ra] < size[rb]:
        ra, rb = rb, ra
    parent[rb] = ra
    size[ra] += size[rb]
print(max(depth(parent, x) for x in range(n)))  # 1

크기 기준으로 합치면 매번 혼자인 원소가 큰 트리의 루트 바로 밑에 붙으므로 최대 깊이가 1에 머뭅니다.

연산당 시간 재 보기

무작위 union을 20만 번 실행하면서 원소 수를 천 배로 늘려 봅니다. 연산당 시간은 수 마이크로초 수준에 머물며 n에 비례해 커지지 않습니다. 실행 환경에 따라 조금 늘어나는 경우가 있는데, 대부분 배열이 커져 메모리 캐시에 덜 들어맞기 때문이고 알고리즘의 연산 횟수 때문은 아닙니다.

import random
import time

def ns_per_op(n, m=200_000):
    parent, size = list(range(n)), [1] * n
    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x
    start = time.perf_counter()
    for _ in range(m):
        ra, rb = find(random.randrange(n)), find(random.randrange(n))
        if ra != rb:
            if size[ra] < size[rb]:
                ra, rb = rb, ra
            parent[rb] = ra
            size[ra] += size[rb]
    return (time.perf_counter() - start) / m * 1e9

for n in (10**3, 10**5, 10**6):
    print(n, f"{ns_per_op(n):.0f} ns/op")

공간 복잡도

parent와 size(또는 rank) 배열 두 개면 되므로 공간은 O(n)입니다. 랭크는 log n을 넘지 않으므로 아주 작은 정수 형식으로도 충분합니다. 재귀로 find를 구현하면 최악의 경우 호출 스택이 트리 높이만큼 쌓이므로, Python처럼 재귀 한도가 낮은 언어에서는 반복문 구현이 안전합니다.

import sys
# 재귀 find를 꼭 써야 한다면 한도를 올려야 할 수 있다
sys.setrecursionlimit(1 << 20)

def find_rec(parent, x):
    if parent[x] != x:
        parent[x] = find_rec(parent, parent[x])
    return parent[x]

다른 방법과 비교

정리

두 최적화를 함께 쓴 유니온 파인드는 m번 연산에 O(m α(n)) 시간, O(n) 공간을 씁니다. α(n)은 현실의 어떤 입력에서도 4 이하이므로 사실상 상수로 봐도 됩니다. 간선 삭제가 필요 없고 질의가 많다면 BFS나 DFS를 반복하는 것보다 훨씬 효율적입니다.