[사전정보] Big-O 표기법 (+보충)

빅오표기법

 알고리즘의 효율성을 표기해주는 표기법으로, 데이터의 개수가 주어졌을 때 기본연산의 횟수를 말한다. 

 보통 알고리즘의 시간 복잡도(효율성)와 공간 복잡도(메모리)를 나타내는데 주로 사용된다. 

 

이러한 시간과 공간 복잡도는 빅오, 빅오메가, 빅세타 세가지 표기법이 존재한다.

 하지만 빅오 표기법이 상한선 기준으로 효율성을 표기하기 때문에,  빅오 표기법을 주로 사용한다. (즉, 그래프가 위로 향할수록 비효율적임을 의미) 

 

*빅오메가는 하한선 기준, 빅세타는 상한선과 하한선을 기준으로 한다. 

 

 수학적 빅오 표기법

  모든 n >= n0에 대하여, k * g(n) >= f(n) 인 양의 상수 k와 n0 이 존재하면 f(n) = O(g(n))이다.

       

    f(n)은 내가 짠 알고리즘의 효율성이고 n을 매우 큰 수로 생각했을 때,   

       f(n) = n+5

       g(n) = n

    이라고 한다면,  f(n) <= k*g(n)  부등호가 성립하는 k값이 존재하기 때문에, f(n)은 빅 오 표기법을 통해 O(n) 이라고 나타낼 수 있다. 

    (쉽게 말해, 무한대에 가까운 n을 넣더라도 k*g(n) 보다 클 수 없으면 O(g(n))이라고 나타내는 것이다)

 

 

  특징

  1. 상수항은 신경쓰지 않는다. 빅오 표기법은 데이터입력값이 충분히 크다는 것을 가정하기 때문에 상수항은 무시된다. 

  2.영향력이 없는 항을 무시한다. 차수가 가장 높은 항이 가장 큰 영향을 주므로 이외의 것은 무시한다.  

 상수 < 로그 < 다항 < 지수

 지수에 가까울수록 효율성이 떨어진다.