빅-오 표기법(Big-Oh Notation)

빅-오 표기법(Big-Oh Notation)

빅오 표기법이란 함수 T(n)인 시간복잡도에서 가장 영향력이 큰 부분이 

어디인지 따져보는것이다.

영향력이 큰 부분이 어디인지를 찾기위해선 다음과 같은 예를 들것이다.

이러한 식이 있을때 이식에 대한 근사치(approximation)의 식을 구할 수 있을것이다.

위의 함수에 대한 근사치식을 구성해보면

이러한 식으로 나타낼 수 있을것이다.

+1쯤이야 가볍게 넘어가도 좋다 생각할수 있지만 

여기서 더 간략화 시켜도 프로그램에 무리가 없을까?

조금더 간략화 시켜보겠다.

이렇게 간략화 시킬 수 있을것이다.

하지만 이런 상황에서 2n을 빼버려도 괜찮은지 의문의 생각이 들 수도 있을것이다.

그렇다면 위의 식에서 n의 갯수가 늘어날수록 n^2이 차지하는 비율을 확인해 보자.

이러한 비율을 나타내는것으로 볼 수 있을것이다.

위의 표를 보는바와 같이 n^2가 차지하는 비율은 아마 99퍼 정도 일 것이다.

이런식에 대해 2n과 +1은 별 차지가 없기때문에 간략화 시킬 수 있는것이다.

따라서 2n+1을 제거하여 간략화 시키면 다음과 같이 나타낼 수 있다.

그리고 이 함수를 빅-오 표기법으로 표현한다면

으로 나타낼 수 있다.

빅오 표기법을 구하기 위해선 어떠한 방법을 써야될까?

위에서 설명한 내용을 토대로 보면 빅오를 구하는 방법은

T(n)이 다항식으로 표현된 경우, 최고차항의 차수가 빅-오가 된다.

예를들어 몇가지를 보여주겠다.

이렇게 최고차항의 차수만을 가지고 빅오라고 표현한다.

하지만 최고차항의 차수라고 그 앞에 있는 상수를 지워버려도 되는지 의문이 들 수 도있다.

빅오는 데이터의 수의 증가에 따른 연산횟수의 증가형태(패턴)을 나타느낸 표기법이므로 

차수 앞에 어떠한 수가 있어도 그수는 패턴을 좌이우지하지 않기 때문에 생략해도 된다.

대표적인 빅-오

빅오에도 여러가지의 대표적인것이 있기때문에 알아두면 좋다.

상수형 빅-오

먼저 상수형 빅-오를 보면

이렇게 표현할 수 있다. 

이는 데이터 수에 상관없이 연산횟수가 고정인 유형의 알고리즘이다.

즉 연산횟수가 3이라 할지라도 (1)을 쓴다.

그이유는 상수형 빅-오는 연산횟수가 고정인 유형의 알고리즘이라고 대표하기 떄문이다.

로그형 빅-오

로그형 빅-오를 보면

이렇게 표현할 수 있다.

이는 데이터 수의 증가율에 비해서 연산횟수의 증가율이 훨씬 낮은 알고리즘이다.

로그형 빅-오는 매우 바람직한 유형이다.

선형 빅-오

선형 빅-오를 보면

이렇게 표현할 수 있다.

이는 데이터의 수화 연산횟수가 비례하는 알고리즘이다.

선형로그형 빅-오

선형로그형 빅-오를 보면

이렇게 표현할 수 있다.

이는 n과 logn을 곱한 형태이고

데이터의 수가 두배로 늘때, 연산횟수는 두배를 조금 넘게 증가하는 알고리즘이다.

제곱형 빅-오

제곱형 빅-오를 보면

이렇게 표현할 수 있다.

이는 제곱, 세제곱에 해당하는 연산횟수를 요구하는 알고리즘이다.

이것은 이중 삼중으로 중첩된 반복문의 사용형태라고 볼 수 있다.

지수형 빅-오

지수형 빅-오를 보면

이렇게 표현할 수 있다.

이는 지수적증가 라는 매우 안좋은 연산횟수의 증가를 보이기때문이다.

이는 사용하기에 매우 무리가 있고 비현실적인 알고리즘이다.

이제 빅오표기들의 성능을 대소로 정리하자면 이렇게 나타낼 수 있다.

다시 이것들을 그래프로 나타내면 이러한 형태로 나타낼 수 있다.

이것으로 빅오에 대한 정리는 거의 다 된것같다.