ArrayList 클래스 2 & amortized analysis(분할 상환 분석)

>>>>>>> 소스코드.git

 

다음은 인덱스와 요소를 인자로 받는 add 메서드이다. (MyArrayList.java)

public void add(int index, T element) {
    if (index < 0 || index > size) {
        throw new IndexOutOfBoundsException();
    }
    // 크기 조정을 통해 요소를 추가합니다.
    add(element);

    // 다른 요소를 시프트합니다.
    for (int i = size - 1; i > index; i--) {
        array[i] = array[i - 1];
    }
    // 올바른 자리에 새로운 값을 넣습니다.
    array[index] = element;
}

두 인자 버전 메서드인 add(int, T)는 단일 인자 버전 메서드인 add(T)를 호출하고, add(T) 메서드는 새로운 인자를 마지막에 넣는다. 그다음 다른 요소를 오른쪽으로 이동시키고 올바른 자리에 새로운 요소를 넣는다.

 

add(int, T) 메서드를 분류하려면 먼저 add(T) 메서드를 분류해야 한다.

public boolean add(T element) {
    if (size >= array.length) {
        // 큰 배열을 만들어 요소들을 복사합니다.
        @SuppressWarnings("unchecked")
        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 메서드는 선형이다.

 

따라서 add 메서드는 상수 시간일까? 아니면 선형일까? 일련의 n개 요소를 추가할 때의 평균 연산 횟수를 고려하여 이 메서드를 분류한다. 간단하게 두 요소만큼의 공간이 있는 배열로 시작해 본다.

• 첫 번째 add 메서드를 호출하면 배열에서 사용하지 않는 공간을 찾아서 요소 1을 저장한다.
• 두 번째 호출에서도 배열에서 사용하지 않는 공간을 찾아서 요소 1을 저장한다.
• 세 번째 호출에서는 배열의 크기를 변경하고 요소 2개를 복사하고 요소 1을 저장한다. 이제 배열의 크기는 4가 되었다.
• 네 번째에는 요소 1을 저장한다.
• 다섯 번째에는 배열의 크기를 재조정하고 요소 4개를 복사하며 요소 1을 저장한다. 이제 배열의 크기는 8이다.
• 다음 3번의 add 메서드 호출로 요소 3개를 저장한다.
• 다음 add 메서드 호출로 요소 8개를 복사하고 요소 1을 저장한다. 이제 크기는 16이다.
• 다음 7번의 add 메서드 호출로 7개의 요소를 저장한다.

계속해서 해본다.

• 4번의 add 메서드 호출 후에는 요소 4개를 저장하고 2번 복사한다.
• 8번의 add 메서드 호출 후에는 요소 8개를 저장하고 6번 복사한다.
• 16번의 add 메서드 호출 후에는 요소 16개를 저장하고 14번 복사한다.

패턴이 보인다. n번 추가하면 요소 n개를 저장하고 n-2개를 복사해야 한다. 따라서 총 연산 횟수는 n + n-2, 즉 2n-2가 된다.

 

add 메서드의 평균 연산 횟수를 구하려면 합을 n으로 나눠야 해서 결과는 2-2/n이다. n이 커지면 두 번째 항인 2/n는 작아진다. n의 가장 큰 지수에만 관심 있다는 원칙을 적용하면 add 메서드는 상수 시가느로 간주한다.

 

---

 

때때로 선형인 어떤 알고리즘이 평균적으로 상수 시간이 된다는 것이 다소 어색해 보일 수 있다. 핵심은 배열의 크기를 조정할 때마다 배열의 길이가 2배로 는다는 것이다. 이것으로 각 요소를 복사하는 횟수를 제한한다. 그렇지 않고 고정된 양만큼 곱하는 대신에 고정된 양을 배열의 길이에 더한다면 이 분석은 맞지 않다.

 

일련의 호출에서 평균 시간을 계산하는 알고리즘 분류 방법을 분할 상환 분석(amortized analysis)이라고 한다. 핵심 개념은 일련의 호출을 하는 동안 배열을 복사하는 추가 비용이 분산되거나 분할 상환되었다는 것이다.

 

자, add(T) 메서드가 상수 시간이라면 add(int, T) 메서드는 어떨까? add(T) 메서드를 호출한 후에 배열 일부에 반복문을 실행하고 요소를 시프트한다. 이 반복문은 리스트의 끝에 요소를 추가하는 특별한 경우만 제외하면 선형이다. 따라서 add(int, T)는 선형이다.

 

마지막으로 removeAll 메서드이다.

public boolean removeAll(Collection<?> collection) {
    boolean flag = true;
    for (Object obj : collection) {
        flag &= remove(obj);
    }
    return flag;
}

반복문을 돌 때마다 removeAll 메서드는 선형인 remove 메서드를 호출한다. 그래서 removeAll 메서드를 이차로 생각하기 쉽다. 하지만 반드시 그렇지는 않다.

 

이 메서드에서 반복문은 collection인자의 각 요소를 한 번씩 순회한다. collection의 요소가 m개고 제거할 리스트에 요소가 n개 있다면 이 메서드는 O(nm)이다. collection의 크기가 상수라면 removeAll 메서드는 n에 대한 선형이다. 하지만 collection의 크기가 n에 비례한다면 removeAll은 이차이다. 예를 들어, collection이 항상 100개 이하의 요소를 갖는다면 removeAll 메서드는 선형이다. 하지만 일반적으로 collection이 제거할 리스트에 있는 요소의 1%를 포함한다면 removeAll 메서드는 이차이다.

 

문제 크기(problem size)에 관해 이야기할 때 대상이 어떤 크기인지 또는 크기들인지 주의해야 한다. 이 예는 알고리즘 분석에서 반복문의 개수를 세는 유혹적인 지름길의 함정을 보여준다. 반복문이 한 개라면 알고리즘은 보통 선형이다. 반복문 두 개가 중첩되었다면 이 알고리즘은 보통 이차이다.

 

하지만 주의해라. 항상 각 반복문을 몇 번 실행하는지를 생각해야 한다. 반복 횟수가 모든 반복문에서 n에 비례한다면 단지 반복문만 세면 끝이다. 그러나 이 예제처럼 반복 횟수가 항상 n에 비례하지 않는다면 좀 더 고민해봐야 한다.