Algorithm & Data Structure(3) - 빅 오 카테고리

kimseyoung·2023년 1월 13일
0

ComputerScience

목록 보기
4/8

선택 정렬과 버블 정렬

저번 글에서 버블 정렬에 대한 내용을 정리했었는데, 이번엔 먼저 선택 정렬을 알아보겠다. 선택 정렬의 C 코드는 다음과 같다.

#include<stdio.h>

int main() {

    int array[] = {4,2,7,1,3};
    int array_length = sizeof(array)/sizeof(int);

    for(int i=0; i < array_length - 1; i++) {
        int min_index = i;

        for(int j=i+1; j < array_length; j++) {
            if(array[j] < array[min_index]) {
                min_index = j; 
            }    
        }

        int temp = array[i];
        array[i] = array[min_index];
        array[min_index] = temp;        
    }

    for(int k=0; k <array_length; k++) {
        printf("%d", array[k]);
    }

    return 0;
}

버블정렬과의 차이점은, 선택 정렬은 비교후에 교환을 한다는 점으로, 비교 즉시 교환하는 버블정렬과 다르게, 한 번의 패스스루에서 불필요한 교환을 줄이므로서, 패스스루가 마무리 되었을 때, 필요한 교환만이 일어난 다는 점이다. 즉, 무조건 교환은 한 패스 스루당 한번만 일어난다. (최소 값과 시작 값의 교환)

최악의 경우를 고려하였을 때, 모두 역순 정렬 되어있다면, 선택 정렬은 한번의 패스 스루마다 교환이 무조건 한번 일어나게 될 것이다. 버블 정렬의 경우 최악의 상황을 가정 했을 때, N^2의 단계를 거치는데, 선택 정렬은 N^2/2의 단계를 거치게 된다.

원소 개수(N)버블 정렬 최대 단계선택 정렬 최대 단계
55^2=2514(10번의 비교 + 4번의 교환)
1010^254(45번의 비교 + 9번의 교환)
2020^2199(180번의 비교+ 19번의 교환)

둘 다 이차시간을 가지는 알고리즘이지만, 선택 정렬이 더 효율적임을 알 수 있다.

상수 무시하기

하지만, 빅 오 표기법에서는 선택 정렬과 버블 정렬을 정확히 같은 방식으로 설명한다. 다시 한번 상기시키면, 빅 오 표기법은 데이터 원소가 N개일 때 얼머나 많은 단계수가 필요한가라는 핵심 질문에 답한다. 선택 정렬에 대략 N^2/2의 단계수가 걸리므로 선택 정렬의 빅 오 표기는 다음과 같다.

O(N^2/2)

하지만 실제로 선택 정렬을 빅 오로 표현하면 버블 정렬과 똑같이 O(N^2)이다. 이것은 빅 오의 규칙 때문이다.

빅오 표기법은 상수를 무시한다.

빅 오 표기법은 지수가 아닌 수는 포함하지 않는다는 것을 단순히 수학적으로 표현한 문장이다. 표현식에서 이러한 수는 그냥 버린다. 다음은 이러한 표기의 예제이다.

1. N/2 단계가 필요한 알고리즘은 O(N)으로 표현한다.

2. N^2 + 10 단계가 필요한 알고리즘은 지수가 아닌 10을 버리고 O(N^2)으로 표현한다.

3. 2N단계가 필요한 알고리즘은 2를 버리고 O(N)으로 표현한다.

O(N)보다 100배나 느린 O(100N)이라 해도 마찬가지로 O(N)이다.

빅 오로는 정확히 똑같이 표현하는 두 알고리즘에 대해 한쪽이 다른 한쪽보다 100배나 빠를 수 있다. 왜 이러는 걸까? 그럼 이 표현을 왜 쓰지?

빅 오 카테고리

빅 오 표기법은 일반적인 카테고리의 알고리즘 속도만 고려한다.

실제 건물에 비유해서 논해보자. 건물의 종류는 당연히 매우 다양하지만, 단층 단독 주택, 2층 단독 주택, 3층 단독 주택 등이 있다. 층수가 다양한 고층 아파트도 있다.

이를 카테고리로 분류하면, 단독 주택과 아파트가 된다. 두 건물의 크기와 기능이 완전히 다른 것을 고려해보자. 굳이 "이 건물은 2층짜리 집이고, 저 건물은 100층짜리 고층 건물입니다." 라고 비교할 필요가 없는 것이다.

알고리즘의 효율성도 마찬가지이다. O(N) 알고리즘과 O(N^2) 알고리즘의 효율성 차이가 너무 커서 O(N)이 실제로 2N이던 100N이던 알 바 가아니다. 무조건 N^2보다는 빠를걸 알기 때문이다.

우리는 같은 카테고리의 알고리즘들 끼리만 분석할 필요가 있게 되는 것이다.

이제 이러한 같은 카테고리 문제를 분석하기 위해 시나리오 최적화 를 알아보자.

profile
Full Stack Web & Machine Learning (Big Data Analyst, ADsP)

0개의 댓글