[자료구조] 빅오(big-O) 표기법

 

 이 포스팅은 파이썬 알고리즘 인터뷰를 공부하면서 정리한 내용입니다.

 

 출처 : 파이썬 알고리즘 인터뷰

 

---

빅오

 빅오는 입력값이 무한대로 향할때 함수의 상한을 설명하는 수학적 표기 방법입니다.

 

 빅오는 점근적 실행 시간(Asymptotic Running Time)을 표기할 때 가장 널리 쓰이는 수학적 표기법 중 하나입니다.

 

 점근적 실행 시간이란 입력값 n이 커질 때, 즉 입력값이 무한대를 향할 때 함수의 실행 시간 추이를 의미합니다.

 

 충분히 큰 입력에서는 알고리즘의 효율성에 따라 수행 시간이 크게 차이가 날 수 있습니다.

 

 접근적 실행 시간은 달리 말하면 시간 복잡도라 할 수 있습니다.

 

 시간 복잡도(Time Complexity)의 사전적 정의는 어떤 알고리즘을 수행하는 데 걸리는 시간을 설명하는 계산 복잡도(Computational Complexity)를 의미하며, 계산 복잡도를 표기하는 대표적인 방법이 바로 빅오입니다.

 

 빅오로 시간 복잡도를 표현할 때는 최고차항만을 표기하며, 상수항은 무시합니다.

 

 예를 들어 입력값 n에 대해 $4n^2 + 3n + 4$번만큼 계산하는 함수가 있다면 이 함수의 시간 복잡도는 최고차항인 4$n^2$만을 고려합니다. 이 중에서도 상수항은 무시하며 $n^2$만을 고려합니다.

 

 즉, 여기서의 시간 복잡도는 O($n^2$)이 됩니다.

 

---

빅오 표기법의 종류

1. O(1)

 입력값이 아무리 커도 실행 시간은 일정합니다.

 O(1)에 시행되는 알고리즘으로 해시 테이블의 조회 및 삽입이 이에 해당합니다.

 

2. O(logn)

 실행 시간이 입력값에 영향을 받습니다. 그러나 로그는 매우 큰 입력값에도 크게 영향을 받지 않는 편으로 웬만한 n의 크기에 대해서도 매우 견고합니다.

 대표적으로 이진 검색이 이에 해당합니다.

 

3. O(n)

 입력값만큼 실행 시간에 영향을 받으며, 알고리즘을 수행하는 데 걸리는 시간은 입력값이 비례합니다.

 이러한 알고리즘을 선형 시간 알고리즘이라고 합니다.

 정렬되지 않은 리스트에서 최댓값 또는 최솟값 경우가 이에 해당하며 이 값을 찾기 위해서는 모든 입력값을 적어도 한 번 이상은 살펴봐야 합니다.

 

4. O(n logn)

 병합 정렬을 비롯한 대부분의 효율 좋은 정렬 알고리즘이 이에 해당합니다.

 입력값이 최선인 경우, 비교를 건너뛰어 O(n)이 될 수 있으며 팀소트(Timsort)가 이런 로직을 갖고 있습니다.

 

5. O($n^2$)

 버블 정렬 같은 비효율적 정렬 알고리즘이 이에 해당합니다.

 

6. O($2^n$)

 피보나치 수를 재귀로 계산하는 알고리즘이 이에 해당합니다.

 $n^2$보다 $2^n$이 훨씬 큽니다.

 

7. O(n!)

 각 도시를 방문하고 돌아오는 가장 짧은 경로를 찾는 외판원 문제를 브루트 포스로 풀이할 때가 이에 해당합니다.

 가장 느린 알고리즘으로 입력값이 조금만 커져도 계산이 어렵습니다.

 

---

 지금까지 시간 복잡도를 표현하는 빅오에 대해 알아보았습니다.

 

 빅오는 시간 복잡도 외에도 공간 복잡도를 표현하는 데에도 널리 쓰입니다.

 

 또한 알고리즘은 흔히 시간과 공간이 트레이드오프 관계입니다.

 

 실행 시간이 빠른 알고리즘은 공간을 많이 사용하고, 공간을 적게 차지하는 알고리즘은 실행 시간이 느리다는 것을 의미합니다.

 

---

상한과 최악

 빅오는 상한을 의미합니다.

 

 이외에도 하한을 나타내는 빅오메가, 평균을 의미하는 빅세타가 있습니다.

 

 한 가지 중요한 점은 상한을 최악의 경우와 혼동하는 것 입니다.

 

 빅오 표기법은 정확하게 쓰기에는 너무 길고 복잡한 함수를 적당히 정확하게 표현하는 방법일 뿐, 최악의 경우/평균적인 경우의 시간 복잡도와는 아무런 관계가 없는 개념입니다.

 

 빅오에 대해 정리하자면 빅오 표기법은 주어진(최선/최악/평균) 경우의 수행 시간의 상한을 나타냅니다.