분할 상환 분석 (Amortized Analysis)

"이 연산은 최악의 경우 O(n)인데 왜 O(1)이라고 하지?" — 가끔 터지는 비싼 연산의 진짜 평균 비용

파이썬 리스트에 append 를 백만 번 해도 전체가 O(n) 이다. 그런데 append 하나하나를 뜯어보면, 대부분은 값 하나 넣고 끝(O(1))이지만 배열이 꽉 차는 순간에는 더 큰 새 배열을 만들어 전부 복사(O(n))한다. 이렇게 대부분 싸고 가끔 비싼 연산의 비용을 "한 번에 얼마"로 정직하게 나누는 기법이 분할 상환 분석이다.

평균 사례 분석(average-case)과 다르다. 평균 사례는 입력의 확률 분포를 가정하지만, 분할 상환은 확률이 없다 — 어떤 연산 순서에서도 n번의 총합이 보장된다. 최악의 순서에도 성립하는 "보장된 평균"이다.

1. 종합 분석 (Aggregate Method)

가장 단순하다. n번 연산의 총비용 T(n) 을 구한 뒤 n으로 나눈다.

분할 상환 비용 = n번 연산의 총비용 T(n) n

2. 동적 배열을 직접 키워 보기

"추가" 버튼을 누르면 원소가 하나씩 들어간다. 용량이 꽉 차면 배열이 2배로 늘고 기존 원소를 모두 새 배열로 복사한다(노란 깜빡임). 아래 차트에서 빨간 막대가 복사가 터진 순간, 초록 선이 지금까지의 평균 비용이다.

원소 수 n

배열 용량

누적 총비용

평균 = 총비용 / n

—

막대 = i번째 추가 하나의 비용 · 초록 선 = i번째까지의 분할 상환(평균) 비용. 막대는 계속 튀지만 초록 선은 3 아래로 수렴한다.

왜 하필 2배일까? 용량이 1 → 2 → 4 → 8 → … → n 으로 커지면 복사 비용의 합은 1 + 2 + 4 + … + n < 2n 이다(등비급수). 여기에 원소를 넣는 비용 n 을 더해도 총 T(n) < 3n, 나누면 연산당 3 미만 = O(1).

만약 +1씩만 늘리면? 매번 복사가 터져서 1 + 2 + … + n = n(n+1)/2, 분할 상환 비용이 O(n) 으로 폭발한다. "곱셈으로 키우기"가 핵심이다. (Go 슬라이스, C++ vector, Java ArrayList 모두 배수 확장)

3. 은행원 방법 (Accounting Method)

각 연산에 실제 비용 대신 정해진 요금을 매긴다. 요금이 실제 비용보다 많으면 남는 돈을 동전(credit)으로 자료구조에 저축해 두고, 나중에 비싼 연산이 터지면 저축한 동전으로 값을 치른다. 동전이 항상 0 이상이면, 요금의 합이 실제 비용의 합보다 크므로 요금 = 분할 상환 비용의 상한이 된다.

append 1회에 요금 3을 매긴다: 1은 새 원소를 넣는 데 쓰고, 2는 이 원소 위에 동전으로 저축. 배열이 꽉 차 복사가 터지면, 옮겨지는 각 원소가 자기 동전 1개로 이사 비용을 낸다.

저축된 동전

낸 요금 합

실제 비용 합

잔고(동전)

append를 눌러 보세요.

4. 포텐셜 방법 (Potential Method)

은행원 방법의 일반화. 자료구조의 상태에 포텐셜 함수 Φ(저축된 에너지)를 정의한다. 한 연산의 분할 상환 비용은:

ĉ_i = c_i + Φ(D_i) − Φ(D_i−1)

실제 비용 c_i + 포텐셜 변화량. Φ ≥ Φ(시작) 이면 분할 상환 비용의 합 ≥ 실제 비용의 합.

동적 배열에서는 Φ = 2 × (원소 수) − (용량) 으로 잡는다. 복사가 없는 보통 append 는 원소 수가 1 늘어 Φ 가 +2 → ĉ = 1 + 2 = 3. 복사가 터지는 순간엔 c_i 가 크지만 Φ 가 그만큼 확 줄어서 상쇄 → 역시 ĉ ≈ 3. 항상 O(1)이다.

5. 또 다른 고전 예시 — 이진 카운터 증가

k비트 카운터에 +1 을 한다. 최악의 +1 은 0111…1 → 1000…0 처럼 비트 k개를 모두 뒤집어 O(k). 하지만 0에서 시작해 n번 증가시키면? 0번 비트는 매번(n회), 1번 비트는 2번에 1번(n/2회), 2번 비트는 n/4회… 뒤집힌다. 총 뒤집기 ≤ n(1 + 1/2 + 1/4 + …) = 2n → +1 하나당 평균 2번 = O(1).

증가 횟수 n

총 비트 뒤집기

증가당 평균

—

비교 — 최악 1회 vs 분할 상환

연산	최악의 1회	분할 상환	비결
동적 배열 `append`	O(n) (복사)	O(1)	2배 확장 → 등비급수
이진 카운터 `+1`	O(k) (전부 뒤집기)	O(1)	상위 비트는 드물게 뒤집힘
해시테이블 삽입	O(n) (rehash)	O(1)	load factor 넘으면 2배 재해싱
스플레이 트리 탐색	O(n)	O(log n)	회전이 트리를 점점 균형화
두 스택으로 만든 큐	O(n) (통째 이동)	O(1)	각 원소는 딱 한 번만 옮겨짐

코드로 보기 — 배수 확장 vs +1 확장

# 총비용을 세어 분할 상환 비용을 직접 확인
def simulate(n, grow):
    cap, size, total = 1, 0, 0
    for _ in range(n):
        if size == cap:                 # 꽉 참 → 새 배열로 복사
            total += size                # 원소 size개 복사 비용
            cap = grow(cap)
        total += 1                     # 새 원소 1개 삽입
        size += 1
    return total / n                  # 연산당 평균

simulate(100_000, lambda c: c * 2)   # ≈ 2.9  → O(1)
simulate(100_000, lambda c: c + 1)   # ≈ 50000 → O(n) 폭발

왜 중요한가

1. 자료구조를 정직하게, 하지만 유리하게 평가한다. append 를 "최악 O(n)"이라 부르면 실제보다 훨씬 느려 보인다. 분할 상환은 실제 사용 패턴(연속 삽입)의 비용을 정확히 잡는다.

2. 실시간 시스템에서는 조심. 분할 상환 O(1)이라도 "그 한 번"의 복사는 진짜로 O(n) 시간이 걸린다. 프레임마다 마감이 있는 게임·오디오·로봇 제어에서는 이 튐(spike)이 문제라, 미리 reserve() 로 용량을 확보하거나 점진적 재해싱을 쓴다.

3. Big-O · 캐싱 과 이어진다. 해시테이블·동적 배열·스플레이 트리의 "평균 O(1)/O(log n)"은 전부 이 분할 상환 논리 위에 서 있다.