[ 알고리즘 ] 선택 정렬 / 빅오 표기법

오늘 할 포스팅은, 정렬 중 대표적인 정렬인 선택 정렬과 이를 수행하는 시간에 대한 시간 복잡도를 나타내는 [빅오 표기법] 에 대한 내용입니다.

 

알고리즘은 크게 몇 가지의 범주로 나뉩니다.

 

1. 상수시간 : 실행시간이 입력 크기에 의존하지 않으면 알고리즘은 상수시간을 따른다고 함. (ex. 1/ 정말 상수 ) 

 

2. 선형 : 실행시간이 입력의 크기에 비례하면 알고리즘은 [선형] 이라고 함. ( ex) 2n -1 )

 

3. 이차 : 실행시간이 n2 에 비례하면 이 알고리즘을 이차라고 합니다. ( e.x) for 문 안에 for 문이 들어가는 경우  ) 

... 등 

---

2.1 선택정렬이란 ? 

 

선택정렬은 어떤 요소를 선택해서 가장 작은 value 를 찾아 그 index 에 넣는 정렬 알고리즘을 의미합니다.   

 

아래와 같은 코드 예시에서 선택정렬의 시간복잡도가 얼마인지 알아보겠습니다. 

public class SelectionSort {
 
    /**
     * Swaps the elements at indexes i and j. 두 element 를 한마디로 바꾸는 동작 
     */ 
    public static void swapElements(int[] array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
 
    /**
     * Finds the index of the lowest value
     * starting from the index at start (inclusive)
     * and going to the end of the array.
     */
    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;
    }
 
    /**
     * Sorts the elements (in place) using selection sort.
     */
    public static void selectionSort(int[] array) {
        for (int i = 0; i < array.length; i++) {
            int j = indexLowest(array, i);
            swapElements(array, i, j);
        }
    }
}

1)  우선 첫번째로 swapElmenets 라는 함수의 시간복잡도는 [ 상수시간 연산 ] 입니다. 단순히 요소를 읽고 쓰기만 하는

 

것이기 때문에 이에 대한 연산은 상수 연산입니다. 

 

 

2) 두번째 method 인 indexLowest 에 대해서 살펴보겠습니다. 이와 같은 indexLowest 에 관한 연산은 주어진 숫자 start

 

에서 시작해서 for 문을 array 의 length 까지 돌게 됩니다. 비교회수는 n-1 이 되기 때문에 따라서 index Lowest 의 메소

 

드는 선형이 됩니다. 

 

3) 세번째 method 이자 마지막 method 인 selectionSort 도 한번 알아보겠습니다. 이 해당 selectionSort 역시 배열을 정

 

리하는 함수입니다. 이 역시, 해당 i 가 0 부터, n-1 까지 n 번 돌기 때문에 선형 (즉 n 의 시간 복잡도) 가 됩니다 .

 

4) 종합적으로 하면, n (indexLowest) 안에 n(selectionSort) 의 시간 복잡도가 들어있으므로 총 연산횟수는 n2 에 비례하

 

기 됩니다. 

 

---

 

2.2 빅오 표기법

 

어떤 함수 f(n) 을 O(g(n))으로 표현하기 위한 표기법이라고 말씀드리고 싶습니다. 

 

수학적 정의로는 아래와 같습니다 .

 

1. 최고차항만 남기고 다 무시한다. -> n이 엄청 크다고 가정하기 때문

2. 계수도 무시한다.

 

2.3 실습