분할 상환 분석이란 (Amortized Analysis)

yujamint·2025년 1월 28일

PS

목록 보기

10/10

들어가기 전에

한 회사의 기술 면접(라이브 코딩 세션)에서 특정 자료구조를 구현한 적이 있다.
자료구조의 자세한 요구사항은 차치하고 간단하게 설명하자면 Queue와 같은 구조로, offer(삽입) 연산과 poll(최상위 요소 제거 및 반환) 연산을 할 수 있다.
이때 offer 연산은 항상 상수 비용이 소요되고, poll 연산은 일반적으로는 상수 비용이 소요되지만, 최악의 경우 O(n)의 시간복잡도를 갖는다.

구현을 마치고, 최악의 경우에 대한 시간복잡도 분석까지 마친 뒤 다음과 같은 질문을 받았다.

무작위로 offer, poll을 n번 했을 때의 시간복잡도는 어떤가요?

한참을 고민하다가 결국 올바른 답을 하지 못 했다.
poll과 offer를 각각 n/2번 수행했을 때를 생각했고, 최악의 경우를 기준으로 계산하여 결국 O(n^2)이 되겠다고 생각했다.
하지만 답이 아니였고, 면접이 끝난 뒤에 면접관님께 정답이 무엇이었는지 여쭤봤다. 이는 분할 상환 분석과 관련된 내용이었다.

분할 상환 분석이란

일련의 연산을 수행하는 알고리즘의 평균적인 시간복잡도를 분석하는 데 사용되는 기술이다. 최악의 경우를 분석하는 것이 아니라, 평균적인 시간복잡도를 분석하는 이유는 무엇일까?

2개 이상의 연산을 하는 어떠한 자료구조가 있다고 하자. 자료구조의 어떤 연산은 상당한 비용을 소모할 수 있지만, 다른 연산은 비교적 적은 비용을 소모할 수 있다. 그리고 두 연산은 각각 실행되는 빈도 역시 다를 것이다.
예를 들어, element가 추가되거나 제거됨에 따라 크기가 달라지는 동적 데이터 구조가 이에 해당한다. element가 추가됨에 따라 삽입 연산에 resizing이 동반될 수 있는데, 이때는 동적 데이터 구조의 크기에 따라 상당한 비용이 발생할 수 있다. 그렇지만, resizing은 삽입 연산 시에 매번 발생하지 않는다. 즉, 최악의 경우만 놓고 봤을 때는 상당한 비용이 발생하지만 평균적으로는 그렇지 않다는 것이다.

그럼에도 시간복잡도를 분석할 때 각각의 연산마다 최악의 경우를 따지는 것은 실제 성능보다 매우 낮은 결과로 분석될 수 있기 때문에 완벽한 분석 방법이 아니다.

분할 상환 분석은 알고리즘의 전반적인 연산 집합에 대해 비용이 높은 연산, 그리고 비용이 덜한 연산 모두를 함께 고려하여 위와 같은 맹점을 해결하는 분석 기법이다.

분석 방법

분할 상환 분석의 핵심 아이디어는 비용이 많이 드는 작업의 비용을 비용이 적게 드는 여러 작업에 분산하는 것이다. 이름에서 알 수 있듯이 비용이 많이 드는 작업의 비용을 분할하여, 비용이 적게 드는 여러 작업에 상환한다.

하나의 예를 들어보자. 동적 배열이 존재한다고 했을 때, 배열에 element를 삽입하는 비용은 1이다. 하지만 배열의 capacity를 넘기는 순간에는 배열의 크기를 조정하는 동작이 발생한다. 배열의 크기를 조정할 때의 시간복잡도는 O(n)이라고 하자. (새로운 크기의 배열을 생성한 뒤, 기존 element n개를 복사한다.)
따라서 삽입 연산의 시간복잡도를 최악의 경우로 분석한다면 O(n)이라고 할 수 있다. 그렇다면 이러한 삽입 연산을 n번 했을 때의 시간복잡도는 어떨까? 앞서 언급한대로 간단하게 최악의 경우로 분석한다면 O(n)의 작업을 n번 수행하므로 O(n^2)일 것이다.

하지만 분할 상환 분석은 이를 다르게 분석한다. 결론부터 말하자면, 삽입을 n번 하더라도 상수 비용이 발생한다.
삽입 연산에서는 배열 크기 재조정이라는 고비용의 연산이 발생하긴 하지만 가끔 발생할 뿐이므로, 전체적으로는 그 비용이 높지 않다는 것이다.

위 그림을 참고하자. 초기 크기가 1인 동적 테이블(배열)에 element를 10개 넣으면서 발생하는 비용을 분석한 것이다. 즉, n = 10일 때 삽입 연산을 n번 하는 것이다.

우선 n개의 데이터를 넣기 때문에 1*n 의 비용이 발생한다.

그리고 Amortized Cost(상각 비용) 부분을 확인하면 재조정 비용을 2n으로 계산하는 것을 확인할 수 있다. 2n은 재조정에서 발생하는 비용을 정확하게 계산한 값은 아니고, n을 기준으로 그 비용의 상한선을 정한 것이다. 왜 그런지 확인해보자.

배열의 크기를 2배씩 늘리며 재조정한다는 가정 하에, 배열의 크기는 2의 거듭제곱 즉, 2^k의 크기를 갖는다. (1 -> 2 -> 4 -> 8 -> ...)
이때 2^k는 n개의 element를 충분히 담을 수 있는 크기여야 한다. 즉, n <= 2^k가 성립한다. 예를 들어, 8개의 element를 담기 위해서는 2^3의 크기면 충분하고, 9개의 element를 담기 위해서는 2^4의 크기가 필요하다.

즉, n개의 element를 담기 위해서는 배열의 크기가 2^k로 재조정돼야 한다. 이때 발생하는 재조정 비용은 다음과 같다.

2^0 + 2^1 + 2^2 + ... + 2^(k-1) = 2^k - 1

2^k는 위에서 설명했듯이 n개의 데이터를 담을 수 있으면서 제일 작은 2의 거듭제곱이다. 즉 n 이상의 크기이며, 최대 2n개의 데이터를 담을 수 있는 크기인 것이다. 2n+1개의 데이터를 담기 위해서는 2^(k+1)의 크기가 필요하다. 따라서 다음과 2^k는 같은 범위를 갖는다.

n <= 2^k <= 2n

이제 우리는 2^k가 n개의 데이터를 담기 위한 동적 배열의 크기라는 것을 알고 있고, 2^k의 상한값이 2n이라는 것을 알 수 있다.

따라서 element를 n번 추가하는 비용 n, 그 과정에서 배열의 크기를 재조정하는 비용 2n이 발생한다. n번의 연산 속에서 총 3n의 비용이 발생하는 것이므로 평균적인 비용은 3이라는 상수 비용이 발생하는 것이다.

Java의 ArrayList는?

이러한 개념은 역시 Java의 동적 데이터 구조인 ArrayList에서도 적용된다.

The size, isEmpty, get, set, iterator, and listIterator operations run in constant time. The add operation runs in amortized constant time, that is, adding n elements requires O(n) time. ...

위 설명은 ArrayList의 Javadoc 내용을 가져온 것이다. element를 삽입하는 add 연산이 상각된 상수 시간으로 실행된다는 것을 확인할 수 있다.

정리

분할 상환 분석은 고비용 연산(현재 예시에선 배열 크기 재조정)의 비용을 단순히 최악의 경우로 분석하지 않고, 전체 주어진 시간 내에서 적절한 상한을 찾는다.
위에서 들었던 예시에 따르면, n번의 삽입 연산을 최악의 경우로 분석했을 때도 O(n^2)이라는 상한이 주어진다.
하지만 분할 상환 분석의 목적은 고비용 연산과 저비용 연산의 집합이 주어졌을 때, 평균적인 성능을 계산함으로써 실제 성능보다 매우 낮은 결과로 분석되는 것을 막는 것이다. 그런 이유에서 상한을 보다 엄격하게 잡고, 엄격한 상한을 통해 성능을 분석하는 것이다.

서론에서 내가 잘못 계산한 O(n^2)은 O(1)의 연산과 O(n)의 연산이 각각 n/2번씩 실행된다는 가정을 전제로 한 평균의 경우 분석을 통해 나온 결과였다. 이는 분할 상환 분석과 비교했을 때, O(n)의 연산이 드물게 발생한다는 것을 고려하지 않은 분석이다.

실생활을 예시로 한 자세한 설명 및 분석은 가젤 님의 블로그를 통해 확인해 볼 수 있다.