빅오(big - O)에 대하여

빅오는 점근적 실행 시간(Asymptotic Running time)을 표기할 때 가장 널리 쓰이는 수학적 표기법 가운데 하나다. 점근적 실행 시간이랑 입력값 n이 커질 때, 즉 입력값이 무한대를 향할 때 lim 함수의 실행 시간의 추이를 의미한다. 알고리즘은 궁긍적으로는 컴퓨터로 구현되므로, 컴퓨터의 빠른 처리 능력을 감안한다면 아무리 복잡한 알고리즘도 입력의 크기가 작으면 금방 끝나버린다. 그러므로 관심의 대상이 되는 것은 입력의 크기가 충분히 클 때다. 충분히 큰 입력에서는 알고리즘의 효율성에 따라 수행 시간이 크게 차이가 날 수 있다.

 

점근적 실행 시간은 달리 말하면 시간 복잡도라 할 수 있다. 시간 복잡도(Time Complexity)의 사전적 정의는 어떤 알고리즘을 수행하는 데 걸리는 시간을 설명하는 계산 복잡도(Computational Complexity)를 의미하며, 계산 복잡도를 표기하는 대표적인 방법이 바로 빅오다. 

빅오로 시간 복잡도를 표현할 때는 최고차항만을 표기하며, 상수항은 무시한다. 입력값 n에 대해 4n^2+3n+4번만큼의 계산하는 함수가 있다면 이 함수의 시간 복잡도는 최고차 항만인 4n^2만을 고려한다. 이 중에서도 상수항은 무시하며 n^2만을 고려한다. 즉 여기서의 시간 복잡도는 O(n^2)가 된다. 

 

이처럼 시간 복잡도를 표기할 때는 입력값에 따른 알고리즘의 실행 시간의 추이만을 살피게 된다. 이 추이에 따른 빅오 표기법의 종류는 다음과 같다.

 

• O(1)

입력값이 아무리 커져도 실행 시간은 일정하다. 최고의 알고리즘이라 할 수 있다. 상수 시간에 실행된다 해도 상수 값이 상상을 넘어설 정도로 매우 크다면 사실상 일정한 시간의 의미가 없다. 테이블의 조회 및 삽입이 해당된다.

• O(log n)

입력값에 의해 실행 시간이 영향을 받는다. 그러나 로그는 매우 큰 입력값에도 크게 영향을 받지 않는 편으로 웬만한 n의 크기에 대해서도 매우 견고하다. 대표적으로 이진 검색이 있다.

 

• O(n)

입력값 만큼 실행 시간에 영향을 받으며 , 알고리즘을 수행하는데 걸리는 시간은 입력값에 비례한다. 이러한 알고리즘을 선형 시간(Linear-Time) 알고리즘이라고 한다. 정렬되지 않은 리스트에서 최댓값 또는 최솟값 경우가 이에 해당하며 이 값을 찾기 위해서는 모든 입력값을 적어도 한 번 이상은 살펴봐야 한다.

 

• O(n log n)

병햡 정렬을 비롯한 대부분의 효율 좋은 정렬 알고리즘이 이에 해당한다. 적어도 모든 수에 대해 한번 이상은 비교해야 하는 비교 기반 정렬 알고리즘은 아무리 좋은 알고리즘도 O(n log n) 보다 빠를 수 없다. 입력값이 최선인 경우 , 비교를 건너뛰어 O(n)이 될 수 있으며 팀 소트(Tim sort)가 이런 로직을 갖고 있다.

 

• O(n^2)

버블 정렬 같은 비효율적인 정렬 알고리즘에 해당한다.

 

• O(2^n)

피보나치의 수를 재귀로 계산하는 알고리즘이 이에 해당한다. n^2과 혼동하는 경우가 있는데 처음에는 비슷해 보이지만 2^n이 훨씬 더 크다. 몇 번만 계산해도 금방 알 수 있다.

 

• O(n!)

각 도시를 방문하고 돌아오는 가장 짧은 경로를 찾는 외판원 문제를 브루트 포스로 풀이할 때가 이에 해당하며 가장 느린 알고리즘이다.

입력 값이 조금만 커져도 웬만한 다항 시간 내에는 계산이 어렵다.