시간복잡도, big Oh, big O notation표기법

Big-oh 또는 Big-O notation이라고 한다. 

어느 표기법이 정확한지는 모르겠지만, 

여기서는 Big-O표기법이라고 하겠다.

https://en.wikipedia.org/wiki/Big_O_notation

http://web.mit.edu/16.070/www/lecture/big_o.pdf

위 문서나 해외 문서들 또는 번역서들을 보면 Big-oh라고 언급되는 경우는 거의 없었던 것 같다. 반면에 한국의 네이버 검색의 경우 Big-oh라고 사용되는 비중이 높은 듯 싶다. 이런 편중적인 현상은 검색의 힘인가?

아무튼 Big-O 표기법은 알고리즘이 얼마나 효율적인지를 판단하는 대표적인 표기법이다. (전산)수학에서 사용되는 이 표기법은 실제로 프로그래밍을 하는 기법은 아니다. 그러나, 자신이 사용할 자료의 크기에 대해서 어떤 알고리즘이 얼마나 효율적인지를 판단해 주는 척도가 되기 때문에, 대충이라도 알아두는 것이 좋다.

 

Big-O 표기

O(함수)

괄호 안의 함수가 시간복잡도를 나타내며 일반적으로 자료의 크기(개수)에 관한 수식이다.

log₂n, n, nlog₂n, n², n³, 2ⁿ

위 함수들은 시간복잡도를 나타내는 대표적인 함수들이며 위에 쓰인 순서대로 시간복잡도가 높아진다고 볼 수 있다. 이에 대한 이해를 위해서 함수에 따른 시간복잡도의 그래프를 살펴보도록 하겠다.

상수 C에 관한 함수인 상수함수다. 자료의 개수 n과 관련 없이 시간복잡도가 C가 된다.

 

2를 밑으로 하는 로그함수는 n이 커질수록 효율(시간복잡도)이 더욱 좋아지는 성질이 있다. 아래서 볼 지수함수와는 반대의 성격을 지닌다.

 

자료형의 개수가 그대로 시간복잡도를 나타낸다. 선형시간으로 불리기도 하는데 그래프의 모양이 직선(n에 정비례)임을 기억하자.

 

전반적으로 n보다 좀 더 시간복잡도가 높다. 지수함수와 비슷한 형태지만 기울기가 완만하다.

 

지수함수는 자료의 크기가 조금만 커져도 급격하게 시간복잡도가 높아진다. 매우 비효율 적이다.

 

자료의 크기가 1증가할 때마다 시간복잡도는 2배 증가한다. 살펴본 시간복잡도 중에서 가장 효율이 안 좋다.

 

다음의 표는 정보문화사의 게임프로그래머를 위한 자료구조와 알고리즘에서 발췌한 표이다.

표를 보면 알겠지만, log₂n가 압도적으로 효율이 좋고 지수함수는 압도적으로 효율이 낮다는 것을 알 수 있다.

 

사실 프로그래밍을 하다 보면 시간복잡도에 관해 어느 정도는 염두해 두고 어떤 알고리즘이 효율적인지 비교할 정도만 알면 된다. 너무 수학적으로 머리 아프게 분석할 필요는 없다고 생각한다. 자신이 어떤 알고리즘을 연구, 개발한다던가, 학생입장에서 공부해나가는 경우면 좀 더 깊게 공부해야 할 수 있겠지만 말이다.

 

시간복잡도를 계산하는 방법

시간복잡도의 계산은 정밀하지는 않다. 예를 들어 (N+100)²를 풀면 N²+200N+10000 이 되고 N²(시간복잡도가 가장 큰 하나의 항)로 간단히 표현한다.

for문에서 반복되는 수는 대부분 자료형의 크기가 된다.

따라서

O(N)

 

O(N²)

for문이 내부에서 몇 번 돌아가는지에 대해서 계산하면 위와 같은 경우 쉽게 시간복잡도를 구할 수 있다.

O(log₂n)의 경우는 O(n)보다 효율이 좋은 선형시간 이하 알고리즘인데, 이진탐색이 대표적이다. 이런 알고리즘에 대한 예는 앞으로 천천히 개별적인 알고리즘을 다루면서 시간복잡도를 하나씩 파악해 보겠다.