Embian Blog

시간 복잡도에 대해 공부하다가 빅-오에 대한 이야기가 많이 나와 간단하게 정리해 보도록 하겠다. '데이터 수의 증가'에 따른 '연산횟수의 증가 형태를 표현한 것'이 빅-오이다.대표적인 빅-오 표기에 대해 알아보자.

O(1)

-상수형 빅-오라 한다. 이는 데이터 수에 상관없이 연산횟수가 고정인 유형의 알고리즘을 뜻한다.

예를 들면 연산의 횟수가 데이터 수에 상관없이 4회 진행되는 알고리즘일지라도 O(3)이라 하지 않고 O(1)이라 한다.

이렇듯 O(1)에는 연산횟수가 고정인 유형의 알고리즘을 대표한다는 의미가 담겨있다.

O() 

-로그형 빅-오라 한다. 이는 '데이터 수의 증가율'에 비해서 '연산횟수의 증가율'이 훨씬 낮은 알고리즘을 의미한다. 따라서 매우 바람직한 유형이다. 참고로 로그의 밑이 얼마냐에 따라서 차이가 나긴 하지만, 그 차이는 알고리즘의 성능관점에서 매우 미미하기 때문에 대부분의 경우에 있어서 무시가 된다.

O(n)

-이를 선형 빅-오라 한다. 이는 데이터의 수와 연산횟수가 비례하는 알고리즘을 의미한다.

O(n)

-이를 선형로그형 빅-오라 한다. 이는 데이터의 수가 두 배로 늘 때, 연산횟수는 두배를 조금 넘게 증가하는 알고리즘을 의미한다. n 과  을 곱한 형태라서 난해해 보이지만, 알고리즘 중에는 이에 해당하는 알고리즘이 적지 않다.

O()

-이는 데이터 수의 제곱에 해당하는 연산횟수를 요구하는 알고리즘을 의미한다. 따라서 데이터의 양이 많은 경우에는 적용하기가 부적절한데, 이는 이중으로 중첩된 반복문 내에서 알고리즘에 관련된 연산이 진행되는 경우에 발생한다. 달리 말하면 중첩된 반복문의 사용은 알고리즘 디자인에서 그리 바람직하지 못하다고 할 수 있다.

O()

-데이터 수의 세 제곱에 해당하는 연산횟수를 요구하는 알고리즘을 의미한다. 이는 삼중으로 중첩된 반복문 내에서 알고리즘에 관련된 연산이 진행되는 경우에 발생한다. 이 역시 그냥 적용하기에는 무리가 있는 알고리즘이다.

O()

-이를 지수형 빅-오라 한다. 이는 사용하기에 매우 무리가 있는 , 사용한다는 것 자체가 비현실적인 알고리즘이다. '지수적 증가'라는, 매우 무서운 연산횟수의 증가를 보이기 때문이. 처음 알고리즘을 개발했을 때 이러한 성능을 보인다면, 개선의 과정을 거쳐서 현실적인 연산횟수를 보이는 알고리즘으로 수정되어야 한다.

지금까지 설명한 빅-오 표기들의 성은을 대소로 정리하면 다음과 같다.

O(1) < O() < O(n) < O(n) < O()< O() < O()

그래프로 정리해 보면 다음과 같다.