위키득계정 ↗
기술

분할 상환 분석

분할 상환 분석기술
영문명
Amortized analysis
분석 대상
연산들의 연속된 실행
핵심
전체 비용을 통해 연산당 한계를 구함
주의
모든 개별 연산이 항상 빠르다는 뜻이 아님
분할 상환 분석은 연산 하나의 최악 비용만 따로 보는 대신 연속된 연산 전체의 비용을 분석하여 연산당 비용의 한계를 구하는 방법이다. 입력의 확률 분포를 가정하는 평균 경우 분석과는 다르다.

비싼 연산의 빈도

어떤 연산이 가끔 많은 작업을 해도 그 사이에 싼 연산이 충분히 많으면 전체 비용이 작을 수 있다. 분할 상환 분석은 이런 관계를 이용한다. 단지 보통 빠를 것이라는 경험적 추정은 아니다.

동적 배열의 예

배열 용량을 가득 찰 때마다 두 배로 늘린다고 하자. 확장 때는 기존 원소를 복사하므로 비싼 연산이 생긴다. 하지만 빈 배열에서 n번 뒤에 추가하는 동안 복사량을 합하면 O(n)이 되어 추가의 분할 상환 비용은 O(1)이다.

평균 경우와 구별한다

분할 상환의 연산당 평균은 정해진 연산열의 전체 비용을 나누는 의미다. 무작위 입력의 분포를 두고 기대 비용을 계산하는 평균 경우 분석과 같은 주장은 아니다.

어떤 연산열인지 명시한다

추가만 하는 분석과 추가·삭제가 섞인 분석은 조건이 다르다. 용량을 줄이는 규칙을 잘못 정하면 확장과 축소가 반복될 수 있다. 자료 구조의 정책과 허용 연산을 정한 뒤 전체 비용을 분석해야 한다.

관련 문서

시간 복잡도 / 동적 배열 / 배열 / 경로 압축 / 알고리즘 / 공간 복잡도