🔙뒤로가기

어떤 응용 프로그램에서는 LinkedList가 빠르게 동작하고, 다른 프로그램에서는 ArrayList가 빠르게 동작할 수 있다. 어떤 응용 프로그램에서는 LinkedList가 빠르게 동작하고, 다른 프로그램에서는 ArrayList가 빠르게 동작할 수 있다. 이런 접근법을 프로파일링이라고 한다. 그런데 여기에는 몇 가지 문제가 있다.

1. 비교할 알고리즘들을 사전에 모두 구현해야 한다.
2. 결과는 컴퓨터 성능에 영향을 받는다. 컴퓨터의 성능에 따라 특정 알고리즘이 더 빠르게 작동할 수도 있다.
3. 결과는 입력되는 데이터의 크기와 종류에 따라 달라질 수 있다.

이러한 문제들을 해결하기 위해 알고리즘 분석이라는 방법을 사용할 수 있다.

알고리즘 분석 예시

• 알고리즘 A의 실행시간이 입력 n의 크기에 비례함
• 알고리즘 B의 실행시간은 입력 n의 제곱에 비례함
• n의 값이 클 때에는 A가 B보다 빠르다고 기대할 수 있음.

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

• 상수 시간(constant time) 알고리즘의 수행 시간이 입력 데이터의 크기와 관계없이 일정한 시간이 걸리는 경우. 즉 실행 시간이 입력 크기에 의존하지 않는 경우.
  • n개의 배열에서 브래킷 연산([ ])을 사용하여 요소 중 하나에 접근할 때
  • 해시 테이블의 조회 및 삽입
• 선형(linear) 알고리즘의 수행 시간이 입력 데이터의 크기에 비례하여 증가하는 경우.
  • 배열에 있는 요소를 더한다면 n개 요소에 접근하여 n-1번 더하기 연산을 해야 함. 이때 연산(요소 접근과 더하기)의 총 횟수는 2n-1이고 n에 비례함.
  • 배열, 리스트의 순차 검색
• 이차(quadratic) 알고리즘의 수행 시간이 입력 데이터의 크기의 제곱(n²)에 비례하여 증가하는 경우. 실행 시간은 n²에 비례한다.
• 리스트에 있는 어떤 요소가 두 번 이상 나타나는지 알고 싶다고 가정하면, 각 요소를 다른 모든 요소와 비교하는 것이 간단한 알고리즘이다. n개의 요소가 있고 각각 n-1개의 다른 요소와 비교하면 총 비교 횟수는 n²-n 이 된다. 여기서 n이 커질수록 알고리즘의 수행 시간이 n²에 비례하여 증가하게 된다.
• 이중 루프를 사용하는 버블정렬, 삽입 정렬

2.1 선택 정렬

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로부터 시작하는 최솟값의 위치를 찾고(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++){
						// i부터 시작하는 최소값의 위치 j를 찾고
            int j = indexLowest(array, i); 
						// array의 다음 순서에 j를 넣는다.
            swapElements(array, i, j); 
        }
    }
}

swapElements 메소드

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