[Think Data Structues]알고리즘 분석법

알고리즘 분석

---

어떤 응용 프로그램에 어느 클래스가 더 좋을지 결정하는 한 가지 방법은 둘 다 시도해보고 각각 얼마나 걸리는지 알아보는 것인데,

이러한 접근법을 프로파일링(profiling)이라고 하는데 여기에는 몇 가지 문제점이 존재한다. 

• 알고리즘을 비교하려면 사전에 그것을 모두 구현해봐야 한다.
• 결과는 사용하는 컴퓨터 성능에 의존한다.
• 결과는 문제 크기나 입력으로 사용하는 데이터에 의존하기도 한다. 

알고리즘 분석(analysis of algorithm)을 사용하여 이러한 문제점을 해결할 수 있다. 알고리즘 분석은 그것을 구현하지 않고도 알고리즘을 비교할 수있도록 하는데 몇 가지 가정을 해야만 한다.

• 알고리즘을 이루는 더하기와 곱하기, 숫자 비교 등의 기본 연산을 식별한다. 그리고 각 알고리즘에 필요한 연산 수를 센다.
• 입력 데이터의 세부사항을 다루지 않으려면 가장 좋은 선택은 기대하는 입력 데이터에 대한 평균 성능을 분석하는 것이다. 이것이 가능하지 않을 때는 일반적인 대안으로 최악의 시나리오를 분석하기도 한다.
• 작은 문제에서는 최상의 성능을 보이지만 큰 문제에서는 다른 알고리즘이 더 좋을 수 있다는 가능성을 배제하면 안된다. 이때는 보통 큰 문제에 초점을 맞춘다. 작은 문제에서는 차이가 크지 않지만 큰 문제에서는 그차이가 훨씬 거대해지기 때문이다. 

대부분 간단한 알고리즘은 다음 몇 가지 범주로 나뉜다.

• 상수시간
• • 실행시간이 입력 크기에 의존하지 않으면 알고리즘은 상수 시간(constant time)을 따른다고 한다.
  • 배열[] 중 한 요소에 접근 할 때
• 선형
• • 실행시간이 입력의 크기에 비례하면 알고리즘은 선형(linear)라고 한다.
  • 배열[]에 있는 요소를 더한다면 n개의 요소에 접근하여 n-1번 더하기 연산을 해야하므로, 연산 (접근과 더하기)의 총 횟수는 2n-1이고 n에 비례한다.
• 이차
• 실행시간이 n^2에 비례하면 알고리즘은 이차(quardratic)라고 한다.
• 리스트에 있는 어떤 요소가 두 번 이상 나타나는지를 알고 싶다고 가정했을 때, 각 요소를 다른 모든 요소와 비교하는 것 이라고 생각하면 된다. N 개의 요소가 있고 각각 n-1개의 다른 요소와 비교하면 총 비교 횟수는 n^2 - n이 되어 n^2에 비례하게 된다. 

선택정렬 알고리즘 분석

---

public class SelectionSort {
    // i와 j의 위치에 있는 값을 바꾼다.
    public static void swapElements(int[] array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
    
    // start로 부터 시작하는 최솟값의 위치를 찾고 배열의 마지막 위치로 감 
    public static int indexLowest(int[] array, int start) {
        int lowIndex = start;
        for(int i=start; i<array.length; i++) {
            if(array[i] < array[lowIndex]) {
                lowIndex = i;
            }
        }
        return lowIndex;
    }
    
    // 선택 정렬을 사용하여 요소를 정렬 
    public static void selectionSort(int[] array) {
        for(int i=0; i<array.length; i++) {
            int j = indexLowest(array, i);
            swapElements(array, i, j);
        }
    }
}

swapElements 메서드

• 요소를 읽고 쓰는 것은 상수 시간 연산(요소의 크기와 첫 번째 위치를 알고 있다면 한 번의 곱셈과 덧셈으로 어떤 요소의 위치라도 알 수 있기 때문)

indexLowest 메서드

• 반복문을 돌 때마다 배열의 두 요소에 접근하고 한 번의 비교연산을 하므로 상수 시간 연산
• 비교횟수를 계산하면
• start 가 0 일 때, 전체 배열을 검색하고 전체 비교 횟수는 배열의 길이인 n이 됨
• strat가 1 일때, 비교횟수는 n-1이 됨
• 일반적으로 비교횟수는 n-start가 되어 indexLowest 메서드는 선형이 됨

selectionSort 메서드

• 0에서 n-1까지 반복하므로 n번 반복 실행
• 매번 indexLowest 메서드를 호출한 후 상수 시간 연산인 swapElements 메서드를 실행

indexLowest 메서드를 호출할 때마다 연산 횟수는 n에 비례하고, 이를 n번 호출하므로 결과적으로 총 연산 횟수는 n^2에 비례하게 된다.

(출처 : Think Data Structues)