데이터를 덧붙일 때마다 배열 혹은 리스트의 크기가 증가한다.
하지만 자바 같은 언어에서는 배열의 길이가 고정되어있다.
이런 경우, 배열을 만들 때 배열의 크기를 함께 지정해야 한다.
동적 가변 크기 기능이 내재되어 있는 배열과 비슷한 자료구조를 원할 때는 보통 ArrayList를 사용한다.
ArrayList는 필요에 따라 크기를 변화시킬 수 있으면서도 O(1)의 접근 시간을 유지한다.
통상적으로 배열이 가득차는 순간, 배열의 크기를 2배로 늘린다.
크기를 2배 늘리는 시간은 O(n)이지만, 자주 발생하는 일은 아니라서 상환 입력 시간으로 계산 했을 때 여전히 O(1)이 된다.
상환 입력 시간은 왜 O(1)이 되는가?
크기가 N인 배열을 생각해보자.
이 배열의 크기를 늘릴 때마다 얼마나 많은 원소를 복사해야 하는지 역으로 계산해볼 수 있다.
배열의 크기를 K로 늘리면 그 전 배열의 크기는 K의 절반이였을 것이다.
k/2만큼의 원소를 복사해야 한다.
마지막 배열 크기 증가 : n/2개의 원소 복사
이전 배열 크기 증가 : n/4개의 원소 복사
이전 배열 크기 증가 : n/8개의 원소 복사
.
.
.
첫 번 째 배열 크기 증가 : 1개의 원소 복사
따라서 N개의 원소를 삽입하기 위해서 복사해야 하는 원소의 총 개수는
N/2 + N/4 + N/8 + ... + 2 + 1
즉, N보다 작다.
1km 떨어진 곳을 가기 위해
0.5km 걷고 또 0.25km걷고 또 0.125km 걷고...
그렇지만 결코 1km에 다다를 수는 없다.
그래서 N개의 원소를 삽입할 때 소요되는 작업은 O(N)이 된다.
배열의 상황에 따라 최악의 경우 O(N)이 소요되는 삽입 연산도 존재하지만 평균적으로는 각 삽입은 O(1)이 소요된다.
