[Algorithm] 3) 시간복잡도, Big-O 표기법 (2)

https://humanwater.tistory.com/5#comment13773481

[Algorithm] 2) 시간복잡도, Big-O 표기법 (1)

저번 장에서는 알고리즘의 중요한 측정 기준인 시간복잡도를 나타내는 표기법 중, 가장 대표적으로 쓰이는 빅오 표기법(Big-O Notation) 에 대해 알아보았다.

 

그리고 빅오 표기법이 우리에게 어떤 것을 말해주려고 하는지에 대해서도 생각해보았고, 짧은 코드로 실제 어떻게 표기하는 지 까지 알아보았다.

 

O(n^2)의 시간복잡도를 가지는 알고리즘.

O(n)의 시간 복잡도를 가지는 알고리즘.

 

 

그래서 이번 장에는

빅오 표기법

에 어떠한 원리에 의해 표시되어지는 지, 어떤 경우에 사용이 가능한지 수학적인 의미로 조금 풀어보도록 하겠다.

 

위키백과 [ Big-O 정의 ]

 

위키백과에서 나오는 빅오 표기법의 정의를 조금 정리해보자면,

 

 

1) 계속적으로 증가할 수 있는 x 값에 대한 두 함수 f(x), g(x)가 서로

 

2) f(x) <= K * g(x) 라는 조건을 성립할 수 있는,

 

3) 양수 K가 존재한다면,

 

빅오 표기법으로 표시할 수 있다고 되어있다.

 

 

 

위의 말을 정리해보면, 아래 사진과 같다.

( * 극한 함수 표현 때문에 그냥 수기로 썼다. ) 

 

 

 

그리고 위의 함수 g(x) 는,

증가하는 x 값에 가장 크게 영향을 미치는 최고차항으로 표현이 된다.

역시 아래 사진을 보자.

 

 

 

 

이어서, 양수 K 가 존재하는 것을 증명하기 위한 과정은 아래와 같이,

 

 

 

그리고 위와 같이 양수 K 가 존재하는 것을 확인하였다면,

빅오 표기법으로는 이렇게 표시하면,

 

 

 

 

마지막으로, 이 글을 쓰기 전까지만 해도 그냥 단순하게 시간복잡도의 한 기준 이라고만 생각했었던 빅오표기법이였는데, 이렇게 의미를 조금씩이나마 더 알게되고, 실제 사용할 수 있는 상황에 대해서 수학적으로 접근했던 적은 처음인 것 같다. 

 

그리고, 물론 빅오 표기법이 대표적으로 쓰이고 있기 때문에 다른 표기법에 대해서는 자세하게 언급하지 않았는데, 절대 모든 알고리즘이 빅오 표기법만을 좋은 기준의 척도로 보지는 않는다.(그랬다면, 빅 오메가, 빅 세타 표기법은 더 이상 언급조차 되지도 않았을 것이다.) 

 

그래서 이 글을 마치면서, 다른 표기법에 대해서도 어느정도는 알아야 나중에 비교하면서 설명할 수 있을 듯 하다.

( * 그래서 나는 마켓컬리에서 개발자로 근무하고 계신 이종립 님의 사이트를 같이 참고하였다. 꼭 들어가봐라. 고퀄이다. )

 

[참고] https://johngrib.github.io/wiki/big-O-notation/

빅 오 표기법(Big O notation)