빅오 표기법 (알고리즘 효율성)

빅오표기법

보통 알고리즘의 시간 복잡도와 공간 복잡도를 나타내는 용도로 주로 사용

 

 

시간과 공간 복잡도를 나타내는 방법으로는 점근 표기법이라고 해서 빅오(Big-O), 빅오메가(big-Ω), 빅세타(big-Θ) 표기법이 있다.

 

 

그런데 왜? 이 중에서 빅오표기법을 사용했을까?

 

알고리즘 효율성을 상한선 기준으로 표기해서이다.

(상한선 : 알고리즘 효율성은 값이 클수록 즉, 그래프가 위로 향할수록 비효율적임을 의미한다.)

빅오메가는 하한선을 기준으로 하고, 빅세타는 상한선과 하한선의 사이를 기준으로 표기한다.

 

여기서 주의할 점은 빅오 표기법이 상한선만 지정했을 뿐 상한선이 꼭 알고리즘 효율성의 최악의 경우는 아니라는 것이다. 

 

 

상수형을 무시한다.  

 

빅오 표기법은 데이터 입력값(n)이 충분히 크다고 가정하고 있고, 알고리즘의 효율성 또한 데이터 입력값(n)의 크기에 따라 영향받기 때문에 상수항 같은 사소한 부분은 무시한다.

 

 

영향력 없는 항 무시 

 

빅오 표기업은 데이터 입력값(n)의 크기에 따라 영향을 받기 때문에 가장 영향력이 큰 항에 이외에 영향력이 없는 항들을 무시한다.

 

성능비교

그래프에 나와 있는 시간 복잡도의 성능을 비교하면 다음과 같다. (왼쪽에서 오른쪽으로 갈수록 효율성이 떨어진다.)

 

 

( 상수함수 < 로그함수 < 선형함수 < 다항함수 < 지수함수 )

 

 

 

참고 블로그 : 

https://noahlogs.tistory.com/27

빅오 표기법 (big-O notation) 이란