분할 상환 분석(Amortized Analysis)은 Big-O(빅오)와 마찬가지로, 함수의 동작을 설명할 때 중요한 분석 방법 중 하나이다.

분할 상환 분석의 대표적인 예로는 '동적 배열'을 들 수 있다.

동적(Dynamic) 프로그래밍 언어 중 하나인 파이썬은 대부분의 동적 언어들이 그렇듯 정적 배열을 지원하지 않고, '리스트(list)' 자료형만을 동적 배열로써 제공한다.

동적 배열은 미리 초깃값을 작게 잡아 배열을 생성한 후, 데이터가 추가되어 배열이 꽉 찰 때마다, 배열의 크기를 늘려주고 값을 모두 복사하는 방식으로 구현된다.

이때, 배열의 크기를 늘려나가는 배율을 '그로스 팩터(Growth Factor, 성장 인자)'라고 일컫는다.
대개는 더블링(Doubling)이라 하여 그로스 팩터를 2로 한다. (각 언어마다 늘려가는 비율은 상이하다.)

Big-O vs Amortized Analysis

동적 배열에서 데이터를 추가하는 작업의 비용은 O(1)이다.
더블링이 일어났을 때의 비용, 즉 배열의 크기를 늘려주고 값을 모두 복사하는 작업의 비용은 O(N)이다.

그렇다면 동적 배열에서 삽입의 시간 복잡도는 O(N)이라 할 수 있을까?

더블링이 발생하는 경우는 어쩌다 한 번뿐임에도 불구하고 그렇다고 표현하는 것은 지나치게 비관적이고 정확하지도 않다.

이러한 때에 분할 상환 분석을 이용할 수 있다.
이는 최악의 경우를 여러 번에 걸쳐 골고루 나눠주는 형태로 시간 복잡도를 계산하는 분석 방식이다.
이를 통해 동적 배열에서 일어나는 삽입의 시간 복잡도를 Amortized O(1)이라고 표현할 수 있다.

// cpython/Objects/listobject.c
// The growth pattern is: 0, 4, 8, 16, 25, 35, 46, 58, 72, 88, ...
new_allocated = (size_t)newsize + (newsize >> 3) + (newsize < 9 ? 3 : 6)

참고로, 위는 파이썬의 리스트를 구현한 CPython 코드이다.
파이썬의 그로스 팩터 역시 초반에는 2로 설계되어 있으나 전체적으로는 약 1.125로 구현되어 있음을 알 수 있다. (C++의 std::vector는 2, 자바의 ArrayList는 1.5로 구현)