Inor

[Algorithm] Big O 표기법 본문

Algorithm

[Algorithm] Big O 표기법

Inor 2017. 11. 12. 18:07

- 빅 오 표기법


 빅 오 표기법은 프로그램(알고리즘)의 성능을 분석하는 방법들 중 하나로서 최악의 상황을 고려한 시간 복잡도로 표현됩니다. 시간 복잡도란 프로그램이 시작하여 끝나기까지 걸리는 시간을 의미합니다. 빅 오 표기법은 프로그램의 시간 복잡도를 정확하게 나타내는 방법은 아니고 근사치를 나타내는 방법입니다. 그래서 프로그램은 빅 오 표기법으로 표기된 시간 복잡도보다 빠르거나 같게 종료됩니다. 빅 오 표기법은 최고차항만을 사용해서 표기합니다.




- 빅 오 표기법의 종류


 빅 오 표기법을 설명하는 가장 좋은 방법은 프로그래밍 학습과 마찬가지로 코드를 통해서 확인하는 것 입니다. 빅 오 표기법은 O(n), O(1) 등과 같이 앞에 대문자 O를 써주고 안에 시간 복잡도를 표기해주면 됩니다. 빅 오 표기법으로 표현된 코드를 보고 어떤 것의 실행 순서가 가장 빠른지 알아보도록 하겠습니다.



- O(1)


void bigO(){
    int i = 0;              // 1
    cout << i << endl;      // 1
}

 O(1)은 알고리즘에서 입력되는 데이터에 상관없이 항상 코드의 시간 복잡도가 같을 경우입니다. 위의 코드는 입력값에 상관없이 항상 2번의 실행만으로 끝나기 때문에 O(1)로 표기됩니다.



- O(logN)


 logN의 경우에 코드로 나타내기 조금 까다로운데 가장 대표적인 예로 재귀함수를 사용하는 2진 탐색 알고리즘이 O(logN)에 해당합니다. N값이 아무리 많이 증가하더라도 그 증가폭이 미미합니다. 한번 반복할 때 마다 데이터의 절반을 확인한 결과가 나오기 때문입니다. 2진 탐색 알고리즘의 경우에는 트리를 학습하면서 다시 알아보도록 하겠습니다.



- O(N)

void bigO(){
    int n = 0;                      // 1
    int cnt = 0;                    // 1
    cin >> n;                       // 1
    for(int i=0;i<n;i++){           // n + 1
        cnt++;                      // n
    }
}

 위 코드의 모든 시간 복잡도를 더하면 2n + 4이 됩니다. 그러나 빅 오 표기법은 최고차항만을 사용하기 때문에 O(n)이 됩니다.



- O(N^2)


void bigO(){
    int n = 0;                      // 1
    int cnt = 0;                    // 1
    cin >> n;                       // 1
    for(int i=0;i<n;i++){           // n+1
        for(int j=0;j<i;j++){       // ((n*(n+1))/2)+1
            cnt++;                  // (n*(n+1))/2
        }
    }
}

 위 코드의 모든 시간 복잡도를 더했을 경우에 최고차항은 n^2가 됩니다. 그렇기 때문에 빅 오 표기법으로 표기한다면 N(n^2)가 됩니다.




- 빅 오 표기법의 속도(성능)


 빅 오 표기법의 속도 차이는 O(1) < O(logN) < O(N) < O(NLogN) < O(N^2) < O(N^3) < O(2^N) < O(N!)의 순서로 점차 커집니다. 알고리즘의 경우에는 최소한 O(N^2)과 비슷한 수준이나 더 빠르게 동작하도록 설게돼야 합니다.

'Algorithm' 카테고리의 다른 글

[Algorithm] 합병 정렬 (Merge Sort)  (0) 2018.02.02
[Algorithm] 스택을 이용한 큐 구현  (0) 2018.01.25
[Algorithm] Quick Sort (퀵 정렬)  (0) 2017.11.26
Comments