가끔 비싼 연산이 섞여 있어도 여러 번에 걸쳐 평균을 내면 싸다는 것을 보이는 분석 방법 (amortized analysis).
왜 필요한가 — 최악만 보면 오해한다
ArrayList.add()를 생각해 보자. 보통은 배열 끝에 값 하나 넣고 끝이라 O(1)이다.
그런데 배열이 꽉 차면 더 큰 배열을 만들어 전부 복사한다 — 이때는 O(n)이다.
최악의 경우만 보면 → "add는 O(n)이다"
이 말은 맞지만 오해를 부른다. O(n)이 되는 경우는 극히 드물기 때문이다. n번 add 하는 전체 비용을 n으로 나눠 보는 것이 분할 상환 분석이다.
실제로 계산해 보자 — 2배씩 늘리는 경우
용량이 찰 때마다 2배로 늘린다고 하자. n = 16까지 add 할 때 복사가 일어난 총 횟수는
용량 1 → 2 : 1개 복사
용량 2 → 4 : 2개 복사
용량 4 → 8 : 4개 복사
용량 8 → 16 : 8개 복사
──────────────────────
총 복사 = 1+2+4+8 = 15 ≈ n
일반적으로 1 + 2 + 4 + … + n/2 = n - 1 < n 이다.
등비수열의 합은 마지막 항의 약 2배를 넘지 않는다는 성질 때문이다.
총 비용 = n번의 삽입 + n번 미만의 복사 < 2n 평균 비용 = 2n / n = 2 = O(1)
→ 분할 상환 O(1). 개별 연산은 가끔 O(n)이지만 평균은 상수다.
1.5배가 아니라 왜 2배인가 (혹은 그 반대)
| 증가율 | 복사 횟수 | 메모리 낭비 |
|---|---|---|
| 2배 | 적음 | 최대 50% 남을 수 있음 |
| 1.5배 | 조금 많음 | 낭비 적음. 해제한 메모리를 재사용하기 쉬움 |
| +1씩 | 1+2+…+n = n²/2 → O(n) | 없음 |
+1씩 늘리면 분할 상환해도 O(n) 이 된다. 이것이 "2배씩 늘리는 것"의 정당화다.
자바 ArrayList는 1.5배, HashMap은 2배(비트 연산을 위해 2의 거듭제곱 유지)를 쓴다.
평균 시간복잡도와 다르다 — 자주 나오는 함정
| 뜻 | 근거 | |
|---|---|---|
| 평균(average-case) | 입력이 확률적으로 분포할 때의 기대값 | 확률 가정 필요 |
| 분할 상환(amortized) | 연속된 n번의 실제 총비용 ÷ n | 확률 가정 없음. 항상 성립 |
분할 상환은 운에 기대지 않는다. 어떤 입력 순서에서도 n번 연산의 총합이 보장된다. 그래서 더 강한 보장이다.
실무에서 왜 알아야 하나
분할 상환 O(1)이라도 개별 호출은 튈 수 있다.
지연 시간 요구가 엄격한 시스템(게임 루프, 실시간 거래)에서 1000번에 한 번 O(n) 복사가 끼면 그 요청만 100ms 튄다 → p99 지연 악화
→ 크기를 알면 미리 확보한다: new ArrayList<>(10000).
GC나 해시맵 리사이징도 같은 성격의 "가끔 튀는 비용"이다.