1. 분할상환 시간복잡도

• 기존 배열에 동적으로 추가 메모리를 할당할 때 -> 기존 메모리 할당양의 2배수를 할당

분할상환 시간복잡도(Amortized Time Complexity)는 여러 연산을 묶어서 전체 비용을 평균적으로 분석하는 방법입니다.

중요한 점은 확률적인 평균 시간복잡도와 다르다는 것입니다.
"운이 좋으면 평균적으로 빠르다"가 아니라, 어떤 연산 시퀀스가 와도 전체 비용이 일정 수준 이하가 되도록 분석합니다.

vector::push_back()으로 이해하기

예를 들어 capacity가 꽉 찰 때마다 2배로 늘리는 vector가 있다고 합시다.

capacity:  1 → 2 → 4 → 8 → 16 → ...

대부분의 push_back()은 단순히 원소 하나를 추가하므로:

O(1)

하지만 capacity가 꽉 차면:

기존 원소들을 새로운 공간으로 복사

해야 합니다.

예를 들어:

push 1   → O(1)
push 2   → O(1) + 1개 복사
push 3   → O(1) + 2개 복사
push 4   → O(1)
push 5   → O(1) + 4개 복사

그래서 **한 번의 push_back()은 최악의 경우 O(n)**입니다.

그런데 복사 비용을 전부 합쳐 보면:

1 + 2 + 4 + 8 + ... + n

이고, 이 합은:

< 2n

입니다.

따라서 n번의 push_back()에 드는 전체 비용은:

O(n)

이고,

전체 비용 / 연산 횟수
= O(n) / n
= O(1)

즉,

push_back()의 분할상환 시간복잡도는 O(1)

이라고 합니다.

왜 "평균"이라고 하면 안 되나?

예를 들어 8번째 삽입이 이렇게 비싸다고 합시다.

1번째  O(1)
2번째  O(2)
3번째  O(1)
4번째  O(1)
5번째  O(4)
6번째  O(1)
7번째  O(1)
8번째  O(1)
9번째  O(8)

특정 연산만 보면 O(n)까지 올라갑니다.

하지만 비싼 연산이 아무 때나 무한정 발생하는 게 아니라, capacity를 확장할 때마다 이전 원소들을 다시 복사해야 하기 때문에 그 비용이 전체적으로 제한됩니다.

이것이 분할상환(amortization)의 핵심입니다.

InlinedVector와 연결하면

앞에서 이야기한

absl::InlinedVector<int, 4> v;

도 비슷한 관점으로 볼 수 있습니다.

처음 4개까지는 inline storage를 사용하므로 allocation이 필요 없습니다.

1 → 2 → 3 → 4
inline storage

그 이후 capacity를 늘려야 하는 상황에서는 더 큰 storage를 확보하고 원소를 이동시키는 비용이 발생할 수 있습니다.

따라서 개별 확장 연산은 비쌀 수 있지만, capacity를 적절히 증가시키는 전략을 사용하면 전체 삽입 비용을 분할상환하여 분석할 수 있습니다.

정리하면:

최악의 한 번: O(n)
n번 연속 수행한 전체 비용: O(n)
따라서 연산 하나당 분할상환 비용: O(1)

이게 자료구조에서 말하는 분할상환 O(1)의 대표적인 예입니다.