[알고리즘] 알고리즘 성능을 분석하는 상환 분석 (Amortized Analysis)

알고리즘의 성능을 분석하기 위해서 시간 복잡도와 공간 복잡도를 중심으로 한 다양한 방법을 활용한다. 최근에는 컴퓨터 성능이 많이 발전함에 따라 공간 복잡도보다는 시간 복잡도의 중요성이 더욱 높아진 만큼, 시간 복잡도를 중심으로 한 알고리즘 성능 분석 방법 중 상환 분석을 중점적으로 살펴보고자 한다.

 

 

 

상환 분석 (Amortized Analysis)

 

 

알고리즘의 평균 실행 시간을 계산하는 방법으로, 일반적으로 최악인 경우에는 연산 속도가 느리지만 평균적으로는 연산 속도가 빠른 경우에 사용될 수 있다. 하나의 연산을 수행하는 데 필요한 시간을 전체 연산을 수행할 때의 평균 연산으로 바꾸어 생각한다. 

 

 

상환 분석을 위해서는 아래의 세가지 기법을 활용할 수 있다.

 

 

 

Aggregate Method

 

 

class MyArray {
	
    int[] array;	// 데이터를 담을 배열
    int size; 		// 실제 데이터의 크기
    
    public MyArray() {
        array = new int[2]; // 초기 생성 시 배열의 크기는 2
        size = 0;
    }
    
    public void add(int value) {
    	
        // 배열이 가득 찼을 경우, 배열의 크기를 2배로 늘림
        if (size >= array.length) {
            int[] bigger = new int[array.length * 2];
            System.arraycopy(array, 0, bigger, 0, array.length);
            array = bigger;
        }
        
        // 데이터 추가
        array[size] = value;
        size++;
    }

}

 

n번의 연산을 고려하여 복잡도를 계산하는 방법이다.

 

add() 메서드에서, 배열이 가득 차지 않았을 경우 add()의 시간복잡도는 O(1)일 것이다. 하지만 배열의 크기를 변경하면 System.arraycopy() 메서드로 인해 O(n)이 된다. 이때 시간 복잡도를 어떻게 구해야 좋을까? 

 

호출 횟수	연산	배열의 크기
call 1	사용하지 않은 공간에 데이터를 저장	2
call 2	사용하지 않은 공간에 데이터를 저장	2
call 3	새 배열에 데이터 2개를 복사하고 데이터를 저장 (array.length == 4)	4
call 4	사용하지 않은 공간에 데이터를 저장	4
call 5	새 배열에 데이터 4개를 복사하고 데이터를 저장	8
call 6 ~ 8	사용하지 않은 공간에 데이터를 저장	8
call 9	새 배열에 데이터 8개를 복사하고 데이터를 저장	16

 

4번의 add() 메서드를 호출할 때는 데이터를 4개 저장하고, 2개의 데이터를 복사한다.

8번의 add() 메서드를 호출할 때는 데이터를 8개 저장하고, 6개의 데이터를 복사한다.

만약 16번의 add() 메서드를 호출했다면 데이터를 16개 저장하고, 14개의 데이터를 복사해야한다.

 

n번의 연산이 발생할 때의 연산 횟수는 n + (n - 2) = 2n - 2가 된다.

따라서 add() 메서드의 평균 연산 횟수는 (2n - 2) / n이 되어서 상수시간으로 간주할 수 있다.

 

 

 

 

 

Accounting Method

 

 

연산에 따른 비용을 고려하며, 초과된 비용은 나중에 실제로 발생하는 연산에 사용한다. 

 

Stack 연산의 경우, PUSH가 발생하면 향후에 POP이 발생할 것을 예상할 수 있기 때문에 PUSH의 비용을 2로 계산한다. 그리고 이때 초과된 비용은 POP이 발생할 때 사용되므로, POP의 비용은 0으로 잡는다.

 

 

 

 

 

 

Potential Method

 

Amortized cost = 실제 비용+ ΔΦ

 

ΔΦ는 포텐셜 함수의 변화로, 연산 전과 연산 후에 시스템 상태의 변화를 의미한다. 즉, 연산의 실제 비용과 함께 시스템의 상태를 나타내는 포텐셜 함수를 이용해서 비용을 계산하는 방법이다.

 

 

 

 

 

 

 

 

 

 

 

 

이 외의 알고리즘 성능 분석 방법

 

 

Worst-case Analysis

 

 

최악의 경우(최대한 많은 시간이나 공간을 소비할 경우)의 성능을 구한다. 일반적으로 주로 사용되는 방법이며, 빅 오 표기법을 활용한다.

 

 

 

 

Best-case Analysis

 

Worst-case와는 반대로, 알고리즘이 가장 적은 자원을 사용하는 최상의 경우를 파악한다. 자주 사용되지는 않는다.

 

 

 

average-case analysis

 

 

모든 입력 가능한 경우의 확률 분포를 고려하여 알고리즘의 성능을 평가한다. 여기서 P는 확률을, T는 실행 시간을 의미한다.