[자료구조] 시간복잡도와 Big-O 표기

공부용으로 작성되는 페이지입니다. 틀린 부분이나 환경에 따라 오류가 발생할 수 있습니다. 

 

---

 

좋은 알고리즘을 평가하는 척도 : 시간복잡도와 공간복잡도 

 

 

기본적으로 시간복잡도, 즉 속도가 얼마나 빠르냐에 따라서 좋은 알고리즘을 평가하게 된다.

그리고 시간복잡도를 측정하기 위해서 데이터에서 연산 횟수가 얼마나 되는지를 연산해야하는데

이를 알아보는 지표 빅오, 빅오메가, 빅세타 표기법이라고 한다. 각자 최악-최선-평균을 구하는 표기법이다. 

빅오(Big-O) 표기법

시간복잡도를 통한 성능을 측정하기 위해서 보통 빅오(Big-O)를 지표로 삼게되는데,

최악인 상황에서 잘 작동한다는건 결국 어떤 상황에서도 수행이 보장됨을 의미하기 때문이다.

 

빅 오 표기법은  ‘n이 커질 때 알고리즘의 단계가 얼마만큼 증가하는가’ 를 잘 나타내는 표기법으로 n은 데이터를 의미한다. 

빅 오 표기법은... 

 

1. 상수항을 무시한다

 ex)

 

f(n)=5n+3 이라는 식이 있을경우

빅오표기법은 상수항들을 전부 삭제하고 o(n)으로만 표현한다. 

 

2. 영향력 없는 항을 무시한다

ex)

 

f(n)=n^2+5n+100 이라는 식이 있을 경우 

n^2에 비하면 5n이나 100은 영향력을 덜 끼치므로 삭제하고

o(n^2)으로 계산한다. 

 

라는 특징을 가지고 있다.

또한 빅오 표기법에서 O(1) -> O(n!) 순으로 갈수록 비효율적이게 된다. 

여기서 말하는 비효율적 = 실행횟수가 많은 것 을 의미한다.

 

O(1) < O(log n) < O(n) < O(n log n) < O(n 2제곱) < O(2 n제곱) < O(n!)

 

 

 

참고자료

 

[알고리즘] 시간 복잡도와 Big O 표기법