[자바로 배우는 핵심 자료구조와 알고리즘] 2장 알고리즘 분석

알고리즘 분석

프로파일링이란?

• 어떤 응용 프로그램에 어느 클래스가 더 좋을지 결정하는 한 가지 방법은 둘 다 시도해 보고 각각 얼마나 걸리는지 알아보는 것
• 문제점
  1. 알고리즘을 비교하려면 사전에 그것을 모두 구현해봐야 함
  2. 결과는 사용하는 컴퓨터의 성능에 의존함
  3. 한 알고리즘이 어떤 컴퓨터에서는 더 좋을 수 있지만, 다른 알고리즘은 다른 컴퓨터에서 더 좋을 수도 있음
  4. 결과는 문제 크기나 입력으로 사용하는 데이터에 의존하기도 함
• 알고리즘 분석을 사용하면 이런 문제점을 해결할 수 있음
  1. 컴퓨터 하드웨어의 세부사항을 다루지 않기 위해 보통 알고리즘을 이루는 더하기와 곱하기, 숫자 비교 등의 기본 연산을 식별. 각 알고리즘에 필요한 연산 수를 셈
  2. 입력 데이터의 세부사항을 다루지 않으려면 가장 좋은 선택은 기대하는 입력 데이터에 대한 평균 성능을 분석하는 것, 이것이 가능하지 않을 때는 일반적인 대안으로 최악의 시나리오를 분석
  3. 한 알고리즘이 작은 문제에서는 최상의 성능을 보이지만 큰 문제에서는 다른 알고리즘이 더 좋을 수 있다는 가능성을 배제하면 안 됨, 보통 큰 문제에 초점을 맞춤. 작은 문제에서는 알고리즘의 차이가 크지 않지만, 큰 문제에서는 그 차이가 거대해질 수 있기 때문

간단한 알고리즘은 몇 가지 범주로 나뉨

• 상수 시간 : 실행시간이 입력 크기에 의존하지 않으면 알고리즘은 상수 시간을 따른다고 함
  • 예 : n개의 배열에서 브래킷 연산([])을 사용하여 요소 중 하나에 접근할 때 이 연산은 배열의 크기와 관계없이 같은 수의 동작을 수행
• 선형 : 실행시간이 입력의 크기에 비례하면 알고리즘은 선형
  • 예 : 배열에 있는 요소를 더한다면 n개 요소에 접근하여 n-1번 더하기 연산을 해야 함, 연산의 총 횟수는 2n-1이고 n에 비례
• 이차 : 실행시간 n^2에 비례하면 알고리즘은 이차
  • 예 : 리스트에 있는 어떤 요소가 두 번 이상 나타나는지를 알고 싶다고 가정. 간단한 알고리즘은 각 요소를 다른 모든 요소와 비교하는것. n개의 요소가 있고 각각 n-1개의 다른 요소와 비교하려면 총 비교 횟수는 n^2-n이 되어 n이 커지면서 n^2에 비례하게 됨

선택 정렬

선택 정렬 알고리즘 구현

public class SelectionSort {
    public static void swapElements(int[] array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

    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);
        }
    }
}

간단하게 비교 횟수 세기

1. start 인자가 0이면 indexLowest 메서드는 전체 배열을 검색하고 전체 비교 횟수는 배열의 길이인 n이 됨
2. start 인자가 1이면 비교 횟수는 n-1이 됨
3. 일반적으로 비교 횟수는 n-start가 되어 indexLowest 메서드는 선형이 됨

=> n(n+1)/2이고 n^2에 비례. 이것은 selectionSort 메서드가 이차라는 것을 의미

빅오 표기법

모든 상수 시간 알고리즘은 O(1)이라는 집합에 속함, 모든 선형 알고리즘은 O(n)에 속하며 모든 이차 알고리즘은 O(n^2)에 속함
=> 빅오 표기법이라고 함