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

데이터의 수 n과 그에 따른 시간 복잡도 함수 T(n)을 정확히 그리고 오차 없이 구하는 것은 대부분의 경우 쉽지 않다. 

그래서 Big-Oh 표기법을 사용한다.

빅-오라는 것은 함수 T(n) 에서 가장 영향력이 큰 부분이 어딘가를 따지는 것이다. 

이때 사용되는 표기법에 대문자 O, 그러니까 큰 O가 사용되기 때문에 빅-오라고 하는 것이다.

  이것을   이렇게 근사치(approximation) 식을 구성해도 문제가 되지 않는다. 

그 이유는 표를 통해서    에서   이 차지하는 비율을 확인하면 알 수 있다.

				의 비율
10	100	20	120	83.33%
100	10,000	200	10,200	98.04%
1,000	1,000,000	2,000	1,002,000	99.80%
10,000	100,000,000	20,000	100,020,000	99.98%
100,000	10,000,000,000	200,000	10,000,200,000	99.99%

 이 차지하는 비율의 증가를 나타내는 표

표에서 보이듯이  이 차지하는 비율은 절대적이다.   이 조금만 증가해도 이내  이 차지하는 비율은 99%를 넘어선다.

따라서,  은  으로 간략화 할 수 있다.

그리고 이것을 빅-오 표기법으로 표현하면 다음과 같다.

         =>            빅-오 오브         =>            

정리하면 함수  의 빅오는  이며, 이는  의 증가 및 감소에 따른  의 변화 정도가  의 형태를 띰을 의미한다.

간단하게 빅-오 구하기

수학적인 접근 없이 다음 사실을 알면 어렵지 않게 빅-오를 구할 수 있다.

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

예를 들면,

                                      ▶                 

                                     ▶                

                    ▶                

그리고 이것을 일반화화면 다음과 같다.

                 ▶                

즉, 다항식으로 표현된 시간 복잡도 함수 T(n)에서 실제로 큰 의미를 갖는 것은  '최고차항의 차수' 라는 이야기다.

※ 빅-오는 "데이터 수의 증가에 따른 연산횟수의 증가 형태(패턴)" 을 나타내는 표기법이다.

 이것은 다음과 같이 이해해야 옳다.

- "데이터 수의 증가에 따른 연산횟수의 증가 형태를 좌표평면상에 그려놓으면, 증가하는 추세가 둔화되는 형태를 띤다. 즉, 로그 그래프와 유사한 형태를 띤다."

빅-오는 성능 분석에 좋은 도구가 된다.

대표적인 빅-오

'데이터 수의 증가'에 따른 '연산횟수의 증가 형태를 표현한 것'이 빅-오이다 보니, 데표적인 빅오 표기가 존재한다. 이것들은 알아둘 필요가 있다.

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

로그형 빅-오라 한다. 이는 '데이터 수의 증가율'에 비해서 '연산횟수의 증가율' 이 훨씬 낮은 알고리즘을 의미한다. 따라서 매우 바람직한 유형이다. 

참고로 로그의 밑이 얼마냐에 따라서 차이가 나긴 하지만, 그 차이는 알고리즘의 성능관점에서 매우 미미하기 때문에 대부분의 경우에 있어서 무기가 된다.

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

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

데이터 수의 제곱에 해당하는 연산홧수를 요구하는 알고리즘을 의미한다. 따라서 데이터의 양이 많은 경우에는 적용하기가 부적절하다.

이는 이중으로 중첩된 반복문 내에서 알고리즘에 관련된 연산이 진행되는 경우에 발생한다. 

즉, 중첩된 반복문의 사용은 알고리즘 디자인에서 그리 바람직하지 못하다고 할 수 있다.

데이터 수의 세 제곱에 해당하는 연산횟수를 요구하는 알고리즘을 의미한다.

이는 삼중으로 중첩된 반복문 내에서 알고리즘에 관련된 연산이 진행되는 경우에 발생한다. 이 역시 그냥 적용하기에는 무리가 있는 알고리즘이다.

지수형 빅-오라 한다. 이는 사용하기에 매우 무리가 있는... 사용한다는 것 자체가 비현실적인 알고리즘이다.

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

빅-오 표기들의 성능(수행시간, 연산횟수) 의 대소를 정리

   <    <     <     <    <    <