동적 배열의 append는 대부분 빠른데 가끔 오래 걸립니다. 왜 평균 비용과 한 번의 지연을 구분하나요?

동적 배열의 append가 대부분 빠른 이유는 용량이 남아 있을 때 마지막 칸에 바로 쓰기 때문이고, 가끔 느린 이유는 용량이 다 차면 더 큰 연속 영역을 할당해 기존 원소를 옮겨야 하기 때문입니다. 용량을 일정 비율로 늘리면 긴 연산열에서 이동 총량을 append 횟수로 나눈 분할 상환 비용은 작아지지만, 개별 append의 최악 지연이 사라지는 것은 아닙니다.

지연 예산에 맞는 용량 정책을 고릅니다

용량 8인 배열에 아홉 번째 원소를 넣는 순간 새 저장 공간을 확보하고 기존 원소를 복사하거나 이동할 수 있습니다. 그 호출은 원소 수에 비례해 오래 걸리지만, 이후 여러 번은 여유 공간에 바로 기록합니다. 용량을 1, 2, 4, 8처럼 두 배로 키우면 n번 append 동안 복사량은 1+2+4+…의 기하급수 합이며 마지막 항이 n보다 작아 전체가 2n 미만입니다. 개별 초기 원소는 여러 번 이동할 수 있지만, 유한한 n번 연산 전체 비용이 선형으로 묶입니다. 이처럼 전체 연산열의 비용을 각 연산에 나누어 평가하는 분석을 분할 상환 분석(amortized analysis)이라고 부릅니다. ‘상환’은 평균적인 확률 기대값과 달리 특정 연산열 전체에 대한 보장이라는 점도 구분하겠습니다.

성장 배율은 구현마다 다릅니다. 크게 늘리면 재할당 횟수와 복사량은 줄지만 사용하지 않는 여유 메모리와 한 번의 할당 피크가 커질 수 있습니다. 작게 늘리면 공간 낭비는 줄어도 확장과 이동이 자주 일어납니다. 원소가 이동 가능하지 않거나 외부 참조가 있는 언어에서는 복사 대신 참조 무효화, 객체 이동 비용, 안전한 재배치 계약이 추가로 중요합니다.

지연 예산에 맞춰 구조를 고릅니다

예상 크기를 알면 초기 용량을 예약해 첫 확장 지연을 줄일 수 있지만, 실제로 쓰지 않으면 메모리를 선점합니다. 실시간 틱이나 요청 경로처럼 개별 지연 상한이 중요하면 고정 용량 버퍼, 여러 블록으로 나뉜 deque, 사전 할당된 풀을 비교하겠습니다. 반대로 일반적인 배치 처리에서는 분할 상환 처리량과 메모리 효율이 더 중요할 수 있습니다. 배열을 축소할 때도 사용량이 경계 근처에서 오르내리면 늘리고 줄이는 재할당이 반복될 수 있으므로 축소 임계값에 여유를 둡니다.

검증은 평균 append 시간만 보지 않고 확장 시점의 p99·최대 지연, 복사량, 메모리 피크, 참조 유효성을 기록하겠습니다. 성장 직전·직후, 반복적인 확장·축소, 큰 원소와 이동 불가능 원소를 별도로 시험해야 합니다. 결론은 append를 무조건 O(1)이라고 말하는 것이 아니라, 보통은 분할 상환 O(1)이고 특정 호출은 O(n)일 수 있다는 계약입니다.

분할 상환은 무한 실행을 가정하는 표현이 아니라, 임의의 유한한 n번 append 연산열 전체 비용을 n으로 나누어 평가하는 보장입니다. 용량을 1, 2, 4, 8처럼 두 배로 늘리면 재할당 때 복사되는 양은 1+2+4+…로 누적되어 n번 뒤 2n 미만입니다. 초기 원소 하나가 여러 번 이동할 수 있다는 사실과 전체 복사량이 선형이라는 사실을 혼동하면 안 됩니다. 매번 한 칸만 늘리면 이 합이 아니라 1+2+…+n이 되어 전체 비용이 커집니다.

이 보장은 개별 확장 호출의 O(n) 지연을 없애지 않습니다. 한 틱이나 요청의 최대 지연이 중요하면 예상 크기 예약, 고정 용량, 블록 배열을 비교하고 예약으로 인한 메모리 피크를 측정합니다. 배열 버퍼 주소를 외부에 노출했다면 재할당 뒤 참조가 무효화될 수 있으므로 소유권이나 세대 계약을 명시합니다. 성장·축소 임계값이 가까워 반복 재할당이 생기는지도 별도로 시험하겠습니다.

축소 진동은 용량 8에서 원소 4개가 되자 용량 4로 줄이고, 하나를 추가하자 다시 8로 키우는 경우입니다. 이후 추가·삭제를 반복하면 매번 많은 원소를 옮깁니다. 예를 들어 사용량이 용량의 1/4 이하일 때만 절반으로 줄이면 확장 경계와 거리를 두어 이 반복을 완화할 수 있습니다.