amortized time은 어떤 임의의 알고리즘에서, 각각의 연산에 대해 최악의 경우를 따져 계산하지 않고, 오래 걸리는 연산과 오래 걸리지 않는 연산 등을 모두 계산하여 필요한 시간의 평균을 계산하는 방식으로, 이 분석으로 계산한 시간 복잡도는 최악의 경우에서도 평균 수행능력을 보장합니다.
C++에서 동적 배열의 개념으로 사용되는 vector 자료구조에서, push_back 함수의 시간복잡도를 물어보는 형태로 가장 많이 사용되는데, 이는 벡터의 구현 방식에서 확인할 수 있습니다. 벡터는 capacity 만큼 배열을 선언, 배열이 비어 있을 때는 바로바로 값을 삽입($O(1)$) 하며, 배열이 모두 꽉 찼을 경우 현재 크기의 2배의 배열을 allocate 하여 새로운 공간으로 값을 이동 시킵니다. 각각의 연산에 대해 최악의 시간 복잡도를 계산하여 push_back의 시간복잡도를 표현하지 않고, 위의 방식을 이용하여 분석해 봅시다. n번의 연산에서
최악의 경우 : $O(N+1)$, 1번
최적의 경우 : $O(1)$, (N-1)번
즉 , $\frac{N+1+(N-1)}{N} \Longrightarrow O(1)$이 되어, push_back의 시간복잡도는 $amortized \, O(1)$ 라고 할 수 있습니다.