어제 ArrayList의 add메서드를 공부를 했는데 이제 이 메서드를 알고리즘적 측면에서 접근을 해보고자 합니다. 먼저 어제 보았던 add메서드 입니다.
@Override
public boolean add(T element) {
if(size >= array.length) {
T[] bigger = (T[]) new Object[array.length * 2];
System.arraycopy(array, 0, bigger, 0, array.length);
array = bigger;
}
array[size] = element;
size++;
return true;
}어제 배열공간이 부족하면 배열복사가 일어난다고 설명을 드렸습니다. 그렇다면 배열에 아직 사용할 공간이 있다면 add 메서드는 상수 시간이 됩니다. 하지만 배열 크기가 늘어날때는 System.arraycopy 메서드 호출 실행시간이 배열크기에 비례해서 add 메서드는 선형이 됩니다.
(상수시간, 선형 등에 대한 내용은 빅O표기법 정리하면서 설명함)
add 메서드 과정을 책에서 설명하는 대로 정리해보겠습니다. 앞에 숫자는 호출 횟수입니다.
1. add 메서드를 호출하면 배열에서 사용하지 않는 공간을 찾아서 요소 1을 저장합니다.
2. 배열에서 사용하지 않는 공간을 찾아서 요소 1을 저장합니다.
3. 배열의 크기를 변경하고 요소 2개를 복사하고 요소 1을 저장합니다. 이제 배열의 크기는 4가 됩니다.
4. 요소 1을 저장합니다.
5. 배열크기를 재조정하고 요소 4개을 복사하며 요소 1을 저장합니다. 이제 배열의 크기는 8입니다.
6,7,8 연달아 요소 3개저장
9. 메서드 호출로 요소 8개 복사후 요소 1 저장, 크기는 16
이런식으로 반복하면
4번의 add 메서드 호출 후 요소 4개 저장 2 번 복사
8번의 add 메서드 호출 후 요소 8개 저장 6 번 복사
16번의 add 메서드 호출 후 요소 16개 저장 14번 복사
패턴이 보입니다. 시행횟수가 n이면 n개저장 n-2 복사하는 패턴입니다.
따라서 n+n-2 = 2n-2가 됩니다. 여기 까지는 알고 있던 선형인 것 같습니다. 하지만 add 메서드의 평균 연선 횟수를 구하려면 결과값을 n으로 나누어야 합니다. 지금은 add 메서드 호출 시에 (1번) 연산 횟수이기 때문이죠. 2-2/n 결과 값입니다. n이 커질수록 2/n은 작아지고 n의 가장 큰 지수에만 관심 있다는 것을 적용하면 add 메서드는 상수 시간이 됩니다.
여기서 선형 알고리즘이 상수시간이 되어서 뭔가 이상하다고 느꼈는데 add 메서드는 많이 호출할 수록 배열복사하는 주기가 길어지니까 결국에는 상수로 수렴하는 것입니다.
책에서는 이렇게 일련에 호출에서 평균시간을 계산하는 알고리즘 분류방법을 분할 상환 분석(amortized analysis) 위키백과이라고 설명해줬습니다. 이름이 정말 정이 안가지만 동적배열요소에서 중요한 개념이라고 하니 기억하고 있으려고 합니다.
