#6. 빅-오 표기법 (Big-Oh Notation)

이전 #5의 마지막 문단, +1을 생략하는 이유에 이어서 진행된다.

 

빅-오 표기법

T(n) 의 수식에서 실제로 영향력을 끼치는 부분을 '빅-오(Big-Oh)' 라고 부른다.

이 영향력을 끼치는 부분만 표기하는 방법이다.

 

이전 +1 을 생략하는 질문을 다르게 생각해서

+1 이 너무 작은 수치라 생략하는 거라면 +100, +500 과 같이 숫자가 커져도 똑같이 생략하는거냐?

라는 질문을 던질 수 있다.

 

이 대답을 하기에 앞서, 시간 복잡도 함수를 보는데 있어서 그 관점이 어디에 있냐 를 먼저 판단해야 한다.

그 관점이 어딘가 하면 항상 가정하는 최악의 경우, 즉 데이터 표본이 셀 수 없을 많을 때 이다.

 

데이터 표본이 너무 많아서, 예를 들어 10만, 100만의 데이터 중 원하는 값을 찾는다고 할 때

과연 +100, +500 의 수치가 정말 중요할까?

그렇지 않다는 것이다.

 

이처럼 최악의 경우의 수를 가정하고, 핵심이 되는 부분만 표기하는 방법을 빅-오 표기법 이라고 하는 것이다.

 

어디까지 생략해도 되는가

해서

T(n) = n^ + 2n + 1

이라는 함수가 있다고 해보자.

여기서 +1 은 생략해도 된다고 알게 되었다.

 

근데 n의 값에 영향을 받는 2n 은 어떻게 할까?

 : 마찬가지로 생략한다.

해당 표는 각각의 수가 n의 값에 따라 차지하는 수치을 보여준다.

n의 값, 즉 데이터 표본의 수가 많아질 수록 n^ 의 비율이 수식의 대부분을 차지하는 것을 볼 수 있다.

그 말은 2n 의 비중은 점점 줄어든다는 것이고 결론적으로 생략해도 큰 문제가 없다는 것이다.

 

해서 최종적으로

T(n) = n^

으로 표기하고, 이는 빅-오 표기법에 따라

O(n^)

으로 나타낼 수 있다.

 

단순하게 생각해서,

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

라고 보면 된다.

여기서 한가지 의문을 더 가질 수 있는데,

최고차항으로만 나타낸다고 해도

T(n) = a * n^m 이 되어야 할 것 같지만

빅-오 표기법에는 a를 생략했다.

 

이 또한 그래프를 그리면서 보도록 하자.

a배수가 있냐 없냐는 그래프의 가파른 정도, 기울기만 표현할 뿐 비슷한 형태를 취하고 있다.

빅-오 표기법에서는 둘을 결국 같은 패턴으로 본다.

이는 기울기의 정도는 중요하지 않고, 어떤 형태를 취하고 있는지 그 패턴만 중요하다 는 것이다.

 

대표적인 빅-오 그래프

밑의 비교문은 더 연산 횟수가 많아짐을 의미한다.

 

순차 탐색 알고리즘과 같은 표기 O(n) 을 기준으로 봤을 때,

사용하면 안되는 패턴이 두가지가 있다. => O(n^) / O(nLogn)

 

우리는 O(logN) 이나 O(1) 과 같이 O(n) 보다 y축의 값이 작은,

즉 연산 소모 시간이 더 적은 패턴을 지향해야 한다.

 

여기서 O(1), 상수형 빅-오는 n이 어떤 값이든 1번만 시행한다 로 볼 수도 있지만

'정해진 횟수만을 반복한다' 라는 의미로 적용된다.