동적 배열은 논리적으로 연속된 인덱스를 제공하면서 물리 저장소의 용량을 필요할 때 바꾸는 구조입니다. 분석할 때는 한 번의 재할당 지연, 여러 append의 총 이동량, 포인터·iterator의 유효 기간을 서로 다른 계약으로 계산해야 합니다.
append 비용의 상환 O(1)과 개별 지연
배열에 원소를 붙일 빈칸이 있으면 끝에 쓰면 됩니다. 빈칸이 없으면 더 큰 저장소를 확보하고 기존 원소를 옮겨야 합니다. 원소 수를 size, 확보한 칸 수를 capacity라고 구분하면 같은 append가 왜 다른 비용을 가지는지 이해하기 쉽습니다.
상환 O(1)은 긴 연산열 전체의 비용을 연산 수로 나눈 상한입니다. 무작위 입력의 기대값도, 모든 append가 일정 시간이라는 뜻도 아닙니다. 실시간 틱 하나의 지연을 판단할 때는 확장이 일어난 한 호출의 비용을 따로 봐야 합니다.
용량 1에서 아홉 개까지의 확장 추적
두 배 성장, 원소 이동 한 번의 비용을 1로 보는 단순 모형입니다. 실제 언어의 이동·복사·할당 비용과 성장률은 다를 수 있습니다.
| 삽입한 원소 수 | 용량 | 이번 기존 원소 이동 | 누적 이동 |
|---|---|---|---|
| 1 | 1 | 0 | 0 |
| 2 | 2 | 1 | 1 |
| 3 | 4 | 2 | 3 |
| 4 | 4 | 0 | 3 |
| 5 | 8 | 4 | 7 |
| 6~8 | 8 | 0 | 7 |
| 9 | 16 | 8 | 15 |
아홉 번째 append는 기존 원소 8개를 옮깁니다. 하지만 전체 이동은 15개이고, 새 원소 기록 9번을 합쳐도 전체는 n에 비례합니다. 용량이 1,2,4,8,…로 자라므로 복사량의 기하급수 합은 n번 append에서 2n 미만으로 제한됩니다.
그림을 글로 읽기
- 기존 용량 8: 원소 8개로 가득 참
- 새 용량 16 확보: 기존 8개 이동 · 새 원소 1개 기록
- 새 버퍼로 교체: size=9 · capacity=16 · 옛 저장소 정리
- 기존 용량 8 → 새 용량 16 확보: 확장
- 새 용량 16 확보 → 새 버퍼로 교체: 준비 후 공개
성장률을 선택할 때는 평균 이동량만 보지 말고 capacity-size 여유와 재할당 순간의 두 버퍼 보유량을 함께 예산화합니다. 예를 들어 프레임 기한을 넘는 단일 확장이 문제라면 작은 배율로 바꾸는 것보다 예상 최대 크기를 reserve하거나 연속 메모리가 불필요한 블록 구조를 검토하는 편이 더 직접적인 해법일 수 있습니다.
성장률과 공간·이동 비용의 교환
성장 배율 g가 1보다 큰 고정 상수이면 이동 총량은 기하급수 합으로 제한됩니다. g가 1에 가까워질수록 재할당 횟수와 상수 계수가 커집니다. 매번 정확히 한 칸만 늘리면 1+2+…+(n-1)을 옮겨 총 O(n²)이 됩니다.
큰 배율은 여유 공간과 확장 순간의 메모리 피크를 늘릴 수 있습니다. 용량 8에서 16을 새로 확보하면 이 모형에서는 한동안 24칸의 저장소를 동시에 가질 수 있습니다. 실제 할당기는 제자리 확장이나 다른 전략을 쓸 수 있으므로 항상 3배라고 일반화하지 않습니다.
append(value):
if size == capacity:
newCapacity = checked_growth(capacity, minimum=size+1)
newBuffer = allocate(newCapacity)
relocate_existing_elements_safely(newBuffer)
publish_new_storage_and_release_old()
buffer[size] = value
size += 1
이 코드는 원리용입니다. 복사·이동 생성자가 예외를 던지는 타입, 원본을 변경하는 이동, 마지막 삽입의 실패는 언어 컨테이너의 예외 보장에 맞게 처리해야 합니다. 단순한 주소 복사로 모든 객체를 안전하게 옮길 수는 없습니다.
축소 경계와 재할당 진동
용량 8에서 size=4가 됐다는 이유만으로 곧바로 4로 줄인다고 하겠습니다. 원소 하나를 추가하면 size=5가 되어 다시 8칸을 확보하고, 곧바로 하나를 삭제하면 size=4라 다시 4칸으로 옮깁니다. 이렇게 4와 5 사이를 오갈 때마다 원소를 옮기므로 작은 변화가 전체 복사로 증폭됩니다.
확장은 가득 찼을 때, 축소는 사용률이 1/4 이하일 때 절반으로 하는 식으로 두 경계를 벌릴 수 있습니다. 용량 8에서 size=2일 때 4로 줄였다면 다음 한 번의 삽입으로 size=3이 되어도 다시 확장하지 않습니다. 이 간격이 히스테리시스이며, 최소 용량·빈 배열·명시적 reserve·shrink 요청의 정책도 함께 정해야 합니다.
| 선택 | 얻는 것 | 비용 |
|---|---|---|
| 큰 성장 배율 | 적은 재할당 | 여유 공간·피크 증가 |
| 작은 성장 배율 | 공간을 더 촘촘히 사용 | 이동·할당 빈도 증가 |
| 사전 reserve | 알려진 크기까지 확장 지연 감소 | 과다 예약과 시작 비용 |
| 축소 지연 | 확장·축소 진동 감소 | 사용하지 않는 공간 보유 |
| 블록 구조 | 큰 연속 재할당 회피 | 추가 간접 접근·다른 인덱스 비용 |
논리 인덱스와 버퍼 주소의 안정성
재할당 뒤에도 논리 인덱스 3의 원소는 네 번째지만 옛 버퍼의 주소는 무효가 될 수 있습니다. C++ vector 포인터·iterator, Go slice의 backing array 공유 등 언어별 계약을 확인해야 합니다. 포인터 배열은 원소 이동량을 줄일 수 있어도 대상 객체 수명과 간접 접근 비용이 남습니다.
reserve를 했다고 객체 필드의 동시 갱신까지 안전해지지 않습니다. 여러 스레드가 size와 저장소를 바꾸는 경우 컨테이너 자체의 동기화 계약이 필요합니다. 성장 전략과 동시성은 별도입니다.
검증 연습으로 초기 용량 1에서 9번 append를 수행해 누적 기존 원소 이동이 15인지 확인하고, 각 호출의 이동 횟수 최댓값이 마지막 확장의 8인지 별도로 기록합니다. 4↔5 반복 삭제·삽입에서는 즉시 축소 정책이 반복 재할당을 만들고, 1/4 이하 축소 정책은 경계 안에서 용량을 유지해야 합니다. 예상 결과가 다르면 상환 분석과 실제 latency 정책 중 어느 계층이 깨졌는지 먼저 분리합니다.
전체 이동량과 개별 최대 지연
테스트에서 n번 append의 전체 이동 횟수를 세어 두 배 성장에서는 선형으로 증가하는지 확인합니다. 별도로 각 append의 최대 지연, 확장 순간 메모리, 이동 생성·소멸 횟수를 기록합니다. 모두 같은 비용의 정수 배열과 큰 객체 배열의 결과를 섞지 않습니다.
4↔5 반복 패턴으로 즉시 축소와 히스테리시스를 비교하고, 할당 실패·최대 용량·reserve 직후 참조도 확인합니다. 평균 처리량이 좋다는 사실과 한 요청의 기한을 지킨다는 사실은 서로 다른 검증 결과입니다.