쌩초보 빅오 표기법의 원리

 

정보처리기사 준비를 하면서 빅오 표기법을 보고 이게 뭐지? 하고 생각하는 비전공자들이 많을 것이다.

나 역시 비전공자였기에 이해가 안가는 부분은 대충 외워가며 공부를 했다.

그런 쌩초보들을 위해 정말 쉽게 설명하는 빅오 표기원리를 소개한다.

 

일단, 빅오표기법은 점근 표기법의 하나이다. 점근표기법은 함수의 증감추세를 비교하는 표기법이다.

일반적으로 알고리즘의 시간복잡도를 나타내는데 사용된다. 

빅오 표기법에서 헷갈리게 하는 부분이 "="인데 여기서 쓰인 "="는 같다가 아니라 "...정도 된다" 라고 해석하면 된다.

이를테면, O(10n+1) = O(10n) = O(n)  이렇게 표기하면 어떻게 O(10n+1)이 O(n)과 같을 수 있지?

라고 생각하겠지만, n이 무한대로 커진다고 생각해보자. O(10n+1) 에서 "10"이나 "+1"이 큰 의미가 있을까?

다른 예로 O(10+n^2) = O(n^2) 인건데 이것도 n이 무한대로 커진다면 "10+" 큰 의미가 없어지므로 가장 차수가 큰  "n^2"로 표기하는 것이라고 생각하면 쉽다.

즉, (1) 상수나 계수는 무시한다. (2) 가장 큰 차수만 표시한다.  <- 이렇게 생각하면 쉽다.

 

그럼 한 예로 선택정렬의 빅오표기법이 어떻게 계산되는지 보자.

 

선택정렬은 수열에서 최소값을 찾아서 가장 앞쪽의 숫자와 교환하고 라운드를 끝낸다.

두 번째 라운드에서는 첫째 수는 이미 가장 작은 수이기 때문에 나머지 숫자들 중 제일 작은 숫자를 찾아서 두번째 숫자와 자리를 바꾸게 된다. 즉 라운드가 늘어날 때마다 찾아봐야 하는 수가 1씩 줄어든다.

이런 찾기와 교환을 반복해서 작은 수에서 큰 수로 정렬을 하게 된다. 

여기서 하나의 숫자를 확인하는데 걸리는 시간을 Tf라고 하고 n개의 숫자가 대상이면

전부 확인하는데 Tf X n의 시간이 걸린다.

두 수를 교환하는데 걸리는 시간을 Tc라고 하자.  

결국 n개의 숫자를 선택 정렬도 순서를 맞춘다면, 소요시간은 다음과 같이 나타낼 수 있다.

(n * Tf + Tc) +{(n-1) * Tf + Tc).... +(2 * Tf + Tc) + (1 * Tf + Tc) 처럼 나타난다.

여기서 n + (n - 1) + (n - 2) + .... 2 + 1 은 n!이고 n! = n(n+1)/2 로 정리된다.

이를 위에적용한다면, (Tf X n^2)/2 + (Tf/2+Tc) x n이다.

자, 이제 맨 위에서 설명했던 것처럼 n이 무한대로 커진다면, 상수인 (Tf/2+Tc) x n 계수인  Tf/2 를무시하고 가장 큰 차수만 생각한다면 n^2 만 남게 되어 O(n2)이 된다. 

 

또 다른 예로 n이 얼마건 상관없이 일정한 시간이 걸리는 알고리즘의 빅오는 O(1)이다. Stack이나 Push는 n이 얼마건 프로세스당 하나만 처리하므로 시간이 동일하다.

for문 처럼 n의 크기에 따라 선형으로 처리시간이 증가하는 경우는  O(n)으로 표기한다.

 

아래는 효율성이 떨어지는(시간이 오래 걸리는) 순서이다. 

O(1) < O(log n) < O(n) < O(n log n) < O(n^2) < O(2^n)