빅오표기법/빅오분석법(Big O Notation)

http://openparadigm.tistory.com/20

빅오표기법은 간단하게 알고리즘의 성능을 평가할 수 있는 방법이다. 벤치마킹을 통해 실제적인 알고리즘 분석도 가능하지만 어떻게 모든 알고리즘을 전부 테스트하고 사용하겠는가.. 그냥 대충 '각'을 잡아본 후에 사용하는 것이 효율적이다.

이러한 알고리즘 테스트를 위한 여러가지 방법이 있다. 3가지 정도가 있는데 Ω,θ,O 이렇게 세가지이다.
- O표기법은 알고리즘의 최악의 성능을 표시해준다.
- Ω표기법은 알고리즘의 최고의 성능을 표시해준다.
- θ표기법은 정확한 알고리즘의 성능을 표시해준다.
그럼에도 불구하고 O표기법을 많이 사용하는 이유는 '아무리 최악의 상황이라도 이정도의 성능을 보장할 수 있다'라는 것을 보여주기 위해 O표기법을 사용하는 것이다. 괜히 Ω표기법으로 알고리즘을 평가해서 최악을 성능을 내는 경우가 발생하면 기분나쁘잖아 ㅡㅡ;; θ표기법은 사실 알고리즘을 계산으로는 정확히 알기 어렵기 때문에 그닦 많이 사용되진 않는다.

그럼 우리는 O표기법만 알아보자.
다음과 같은 코드가 있다.

void main(){
      int sum = 0;
      int i;

      for(i=1;i<=100;i++){
            sum=sum+i;
      }
      printf("1부터 100까지의 합: %d\n",sum);
}

요런 코드가 있다면 이것은 1부터 100까지 더하는 프로그램이 된다.
이걸 각각의 코드가 몇번 실행 되는지 확인해 보자.

int sum = 0;	1번실행
int i;	1번실행
for(i=1;i<=100;i++){	101번실행(100번실행후 한번 더 실행하는 과정에서 밖으로 빠진다.)
sum = sum + i;	100번실행
printf("1부터 100까지 합:",sum);	1번실행

결국 총 204번이 실행된다. 이것을 빅O표기법으로 표시하면 O(204)가 된다. 쉽죠잉?
"O표기법에서 상수의 존재는 알고리즘의 성능에 아무런 영향을 끼치지 못한다"는 것을 알아두길 바란다.
그럼 O(204)를 O(1)로 간단히 표시하겠다. 앞으로 O(100000)이든 O(3)이든 상수만 들어간 O는 모조리 O(1)로 생각하자.
왜냐하면 위와 같은 코드의 실행 시간은 10번 실행이 10000번 실행보다 빠른게 당연하겠지만 알고리즘 자체로 본다면 데이터의 양이 100 이런식으로 고정되어 있기 때문에(위에 100번 돈다고 했으니까) 다른 입력된 데이터가 많더라도 알고리즘은 여전히 100번만 돌게된다. 즉 입력데이터의 양에 상관없이 성능이 일정하다는 말이다.

근데 만약에 위의 for문이 for(i=1;i<=N;i++) 라고 되어 있다면 어떻게 될까? N번 도는 것이다. N이 얼마인지는 모르겠지만 외부에서 N을 입력받던 계산의 값으로 받던 하여튼 임의의 값이 들어오게 될것이다. 이럴때 우리는 O(N)이라고 표시한다.

여기서 다른 코드를 보자.

이건 최대값을 구하는 코드이다. array[0]을 max에 넣고 for문을 시작한다. array[1]부터 max와 비교하며 array[1]이 max보다 크다면 array[1]을 max에 넣는다. 아니라면 array[2]와 max를 비교한다. 이런식으로 계속 큰 값만 max에 넣으면 배열에 마지막에 가서는 가장 큰값이 max에 있을것이다.

이코드는 총 몇번이 실행되는가? 총 for문은 size-1만큼 실행된다. 편의상 size를 N으로 두자. N-1만큼 실행된다. 이걸 O표기법으로 표시하면 O(N-1)이 된다. 만약 N이 거의 수억천만조경의 값이라면 -1따위야 가뿐히 무시할 수 있는 값이다. 그래서 O(N)으로 표시한다.(O표기법에서 상수란 무용지물이란 말이다..) N의 값이 많아지면 많아질 수록 처리 시간도 그와 비례해서 늘어난다는 의미이다.

위의 코드와 같은 결과를 가지는 아래의 코드를 보자.

int returnMax(int array[], int size){
    if (size < 1) return -1;                       
    bool findMax;                                   
    for (int i = size-1; i > 0; i--) {             
         for (int j = 0; j < size; j++) {          
              if (array[j] > array[i]) {           
                   findMax = false;               
              }
         }
         if(findMax)                               
              break;
    }
    return array[i];
}

위의 코드도 최대 값을 반환한다. 코드를 말로 해석하려 했는데 너무 어렵다 ㅡㅡ;; 그냥 코드를 보시고 이해하길...
보면 알겠지만 이코드는 안쪽 for문에서 N번 반복하고 바깥쪽에서도 N번 반복한다. 다시말해 안쪽의 for문은 N번 반복을 N번이나 한다는 말이다. 물론 최대값이 배열 가장 앞에있는 최악의 경우에 말이다. 이것을 빅오로 나타내면 O(N²)으로 표시할 수 있다. 입력된 데이터의 양(N)에 따라 시간은 그 제곱배로 늘어난다는 말이다.

물론 이코드는 상황에 따라 다르다. 만약 가장 큰값이 가장 끝에 있다면 가장 끝값과 앞에 값들을 각각 한번씩만 비교하면 답이 나오기 때문이다. 이것은 O(N)이된다. 이건 최선의 경우일 때이다. 그리고 평균적으로 계산해 보자면 최대값이 배열 가운데있다면 N번 반복을 N/2번만 하면 되기에 결국 O(N²/2)로 나타낼 수 있다. 그럼 빨라진건가? 그렇지 않다 평균결과는 여전히 O(N²)이다. 왜냐하면 위에서 밝혔듯이 빅오에서 상수의 의미는 없다고 생각하는 것이 좋다고 했다. 책에는 그 이유를 '기계어와 CPU가 처리하는 시간에 따라 결과시간이 달라지기 때문' 이라고 밝혔지만 나도 정확이 이게 무슨말인지는 모르겠다. 여튼 빅오에서는 상수를 무시하고 최고차항이 얼마느냐에만 촛점을 맞추고 있다. 그래서 평균 시간도 O(N²)라고 정의해야한다(고 한다 ㅡㅡ;)

그밖에 경우는 아래와 같다.

O(logN) - 처리 데이터의 양이 증가할 수록 실행시간이 약간씩 증가한다. 하지만 logN의 그래프가 그렇듯이 증가 폭이 급격히 증가하진 않는다. 일반적으로 좋은 효율의 알고리즘이 여기에 해당한다.

O(NlogN) - 처리 데이터의 양의 증가에 대해 처리 시간은 정비례보다 약간 더 많이 증가를 한다. 이것도 효율이 괜찮은 알고리즘일 경우의 계산이다.

O(N³) - 데이터에 양에 대해 세제곱 만큼 시간이 증가하기에 좋은 알고리즘이 아니다. for문이 세번 중첩되면 이꼴이 난다.

O(2^N) - 2의 N제곱이 되는 알고리즘은 거의 최악의 알고리즘 중 하나이다.

아래에 각 결과의 처리시간에 대한 그래프를 가져와 봤다.

<출처 : http://media.photobucket.com/image/o%20notation/amit_9b/BIGO_GRAPH.jpg>

<Big O Notation Graph>

간단하게 빅오표기법을 사용하는 방법을 정리하자면
1. 입력값이 무엇인지 확인한다.(N)
2. 수행 연산 횟수를 N의 식으로 표현한다.
3. 가장 차수가 높은 항만 남기고 그 아래차수와 상수는 날려버린다.

주의점
1. 반복문이 중첩이 아니라 그냥 두개가 나란히 있는경우는 더 높은 차수의 for문을 알고리즘 성능으로 사용한다.
2. 상수가 곱해져 있고 옆에 N이 더 있더라도 최고차수만 사용한다.

+
재귀호출에서의 빅오표기법???? 재귀호출은 덧셈처럼 계산되어서 O(N)으로 사용된다는데 이건 이후에 다시 포스팅하자.