그림 3-7에서 capacity가 size보다 크다면 단순히 마지막 요소 다음에 새로운 요소를 추가하면 됩니다.

문제는 배열이 가득 차 있을 때입니다. 이때는 충분한 공간을 다시 확보하고 기존 배열 요소를 모두 복사한 후 새로운 데이터를 추가해야 합니다. 빅오가 데이터 개수만큼 복사해야 하므로 O(n)이 됩니다. 공간이 충분했을 때는 O(1)이었는데 이번에는 O(n)이라니 배열의 마지막에 데이터를 추가 혹은 삭제하는 연산은 빅오를 무엇으로 정해야 할까요? 이때 유용하게 적용할 수 있는 개념이 분할 상환 분석(amortized analysis)인데요. 책에서는 이 분석법을 자세히 알아보지는 않고 동적 배열에서의 예만 살펴보겠습니다. 미리 결론만 이야기하자면 분할 상환 분석을 이용한 이 연산의 빅오는 O(1)입니다.

다음 그림으로 이 분석의 정당성을 생각해 보죠.

▲ 그림 3-8 동적 배열의 삽입과 삭제 2