할부 시간 복잡도(amortized time complexity)

컴퓨터 프로그램의 시간 복잡도를 계산할 때, 가장 많이 사용되는 것은 최악 시간 복잡도(worst-case time complexity)다. 어떤 입력이 들어왔을 때, 가장 오래 걸리는 시간을 추정하는 것이다. 그 다음으로 많이 사용되는 것은 평균 시간 복잡도(average-case time complexity)다. 시간을 가장 많이 끄는 입력이 천 번에 한 번꼴로만 발생한다면 모든 입력을 최악 조건으로 생각할 필요는 없기 때문이다.

할부 시간 복잡도(amortized time complexity)는 각 입력의 처리시간을 고려한다는 점에서 평균 시간 복잡도와 유사하다. 그러나 각 입력이 들어올 빈도를 별도로 고려하지 않는다는 점에서 평균 시간 복잡도와는 차이가 있다. 할부 시간 복잡도를 계산할 때는 각 입력이 같은 빈도로 발생한다는 가정 하에 복잡도를 계산한다.

예컨대 일시정지 방식의 메모리 재사용 시스템(garbage collector)을 생각해 보면, 평소에는 메모리 재사용 시스템이 가동되지 않다가 메모리가 막상 모자랄 때만 시간이 오래 걸린다. 따라서 최악 조건을 생각한다면 각 할당 명령어의 시간 복잡도는 매우 크게 된다. 그러나 사실 GC 구동을 유발하는 메모리 할당(allocation) 연산만 제외한다면 나머지는 할당 연산에는 그리 큰 시간이 들지 않는다. 따라서 할부 시간복잡도는 현저히 작아지게 된다.