빅 오 표기법

빅 오 표기법은 특정 알고리즘의 시간 복잡도를 나타내는 함수이다. 시간 복잡도란 알고리즘을 실행하는 데 필요한 수행 시간을 의미한다. 

 예를 들어 for문을 이용해 i=0 부터  i<10까지 반복하는 코드가 있다면 이 코드의 시간 복잡도는 10이다. 이렇게 확실하게 반복되는 횟수가 정해진 코드를 상수형 빅 오 라고 부르며 O(1)이라고 표기한다. 실제로 반복되는 횟수는 10이지만 1로 표기하는 이유는 작업 수행 횟수(n이라고 표기)를 무한대로 잡기 때문이다. 즉 언급한 코드를 n = ∞ 로 실행한다 해도 작업 수행 횟수는 항상 10이다. 10이라는 숫자는 무한대인 n보다는 아주 작아서 1로 대체해도 무방하다. 이것은 어떤 상수에도 적용되기 때문에 작업 수행 횟수가 고정되어 있는(특정 상수로 정의되는) 알고리즘은 항상 O(1)의 빅 오 표기법으로 표시한다.

그렇다면 O(1)로 표기되지 않는 알고리즘은 어떤 형태일까? 간단하게 예를 들면 이전에 for문을 다음과 같이 바꿔보자.

for( i = 0 ; i < n ; i++ )

…some code…;

어디가 달라졌는지 금방 눈치챌 수 있다. 이전 코드의 경우 i < 10 으로 반복 횟수가 10으로 고정되어 있었지만, 이번 코드는 i < n 으로 변수 n의 크기에 따라 반복횟수가 바뀌게 된다. n은 사용자가 입력할 수도 있고, 코드 내에서 특정 계산을 통해 나온 결괏값일 수도 있다. 따라서 for문은 n번 반복하기 때문에 작업 횟수는 n이다. 빅 오 표기법으로 나타내면 O(n)으로 표기한다. 

다음과 같은 경우는 어떨까?

for( i = 0 ; i < n + 1 ; i++ )

…some code…;

이번엔 작업 획수가 n + 1로 바뀌었다. 그렇다면 빅 오 표기법으로 O(n+1)로 표기해야 할까?

답은 NO이다. 이 경우도 O(n)으로 표기된다. 앞에서 언급했듯이 n이 무한대로 간다면, 뒤에 +1은 아주 작은 숫자에 불과하다. 

간단하게 n1 = 10000 인 경우와 n2 = 10001 인 경우를 생각해 보자.  n1 과 n2는 거의 같다고 말할 수 있지 않을까? 만약 아니라면 숫자를 더 키워보자. n1 = 1000000000000000000, n2 = 1000000000000000001 이라면… 이제 1은 무시해도 될 만큼 아주 작은 숫자이다. 실제로 n은 이것보다 더 큰 수(셀 수 없는 무한대)이기 때문에 n 말고 다른 상수는 무시하도록 하자. 이 규칙은 다른 사칙연산에도 적용된다. 

n + 1 = O(n)

n + 100 = O(n)

n - 100 = O(n)

2 * n = O(n)

n / 2 = O(n)

곱셈과 나눗셈에 대해 의심이 간다면 따로 조사해 보도록 하자. 개발자에게 구글링은 생명이다.

빅 오 표기법에서 상수가 영향력이 작다는 것을 알았다. 하지만 차수로 올라간다면 얘기가 다르다. 다음과 같은 수행 횟수를 갖는 알고리즘을 생각해보자.

n^2 + n + 1

일단 맨 뒤에 있는 +1 항이 빅 오 표기법에 영향이 없다는 것을 알 수 있다.

O(n^2 + n)

위와 같이 표기하면 될까? 잘 생각해보자. 우리가 상수항을 무시하는 이유는 n이 무한대로 가기 때문이다. 그렇다면 n의 제곱은 n보다 매우 크기 때문에 n을 무시할 수 있다. 

n^2 >>> n

따라서 차수가 다양한 다항식에서는 가장 높은 차수만 빅 오 표기법으로 나타낸다.

O(n^2)

그렇다면 제곱 항을 갖는 다항식을 수행 횟수로 갖는 알고리즘은 어떤 것일까?

가장 간단한 예는 이중 for문이다.

for( i = 0 ; i < n ; i ++ ){

for(j = 0 ; j < n ; j ++ ){

… some code … } }

위와 같이 코드가 짜 인 경우 안쪽에 for문이 n번 반복하는 작업을 바깥쪽 for문에서 n번 반복하기 때문에 n*n의 작업횟수를 갖는다. 예를 들면 구구단을 출력하기 위해 이중 for문을 사용하여 9*9번의 printf문을 출력하는 것과 같다.

간단한 코드의 경우 눈으로 보고 수행횟수를 계산하여 빅 오 표기법으로 바꿀 수 있지만, 복잡한 코드의 경우 바로 보고 빅 오 표기법으로 나타내기 어려운 경우도 있다. 빅 오 표기법을 구하는 일반적인 순서는 다음과 같다.

1. 입력 값이 무엇인지 확인하고 어떤 것을 n으로 놓아야 할지 결정한다.

2. 알고리즘에서 수행해야 할 연산 횟수를 n의 식으로 표현한다.

3. 차수가 제일 높은 항만 남긴다.

4. 모든 상수 인수를 없앤다.

빅 오 표기법은 주로 자료구조에서 정렬이나 검색 알고리즘에 성능을 비교할 때 자주 사용됩니다. 면접이나 필기 문제로는 여러 가지 정렬 방법을 나열하고 빅 오 표기법을 이용해 빠른 순서로 정렬하거나, 특정 문제를 해결하는 데 필요한 빅 오 표기법을 제시한 뒤 그에 알맞은 알고리즘을 선택하는 문제 등이 있습니다. (ex. O(n)의 시간 복잡도를 갖는 검색 알고리즘을 구현하라.)