■ 분할 상환 분석

알고리즘 성능이 나와 있는 자료를 보면 분할 상환 분석(amortized analysis)을 적용하여 ‘이 알고리즘의 복잡도는 분할 상환 상수 시간(amortized constant time)을 가진다’ 같은 표현을 볼 수 있습니다. 분할 상환 분석이란 특정 상황에서는 좋지 않은 성능을 내지만, 나머지 상황에서는 좋은 성능을 낼 때 모든 연산을 고려해 성능을 분석하는 것을 말합니다. 다시 말해 특정 상황에서의 고비용(high cost)을 일정 기간으로 분산시켜(마치 은행 대출금을 분할하여 상환하듯이) 성능을 평가하는 것입니다.

분할 상환 분석의 대표적인 예에는 동적 배열(dynamic array)이 있습니다. 주어진 메모리 공간이 가득 차면 공간을 두 배로 할당받아 기존 요소를 옮긴 후 더 많은 요소를 추가할 수 있는 동적 배열이 있다고 가정합시다. 배열 크기가 요소를 열 개 담을 수 있고 현재 요소가 네 개만 존재하면 배열이 꽉 차기 전까지 새로운 요소를 추가할 때 성능이 O(1)입니다. 요소를 여섯 개 삽입하여 배열이 꽉 차면 요소 스무 개를 담을 수 있는 공간을 확보한 후 기존 배열의 요소를 옮기게 되는데, 이 경우에만 성능이 O(n)입니다. 이후 새로운 요소를 열 개 삽입하는 동안에는 빅오가 다시 O(1) 즉, 상수 시간이 됩니다.

배열 크기를 늘릴 때는 고비용(기존 배열의 요소 열 개를 옮기면서 발생한 비용)이 발생하지만 이후 요소 열 개를 추가하는 동안에는 비용이 거의 들지 않으므로 이 기간 동안에 분산시키면 성능은 상수 시간과 비슷해집니다. 이를 분할 상환 상수 시간(amortized constant time)이라고 합니다.

분할 상환 분석 기법을 사용하면 연산마다 최악의 경우를 계산하지 않아도 되므로 성능 분석을 좀 더 쉽게 할 수 있습니다.

다음 절부터는 정렬 알고리즘 중 거품 정렬과 퀵 정렬에 대해 알아보겠습니다. 지금부터 설명할 정렬 알고리즘에서 정렬 기준은 오름차순입니다.