[알고리즘] 빅오(big-O)

빅오란?

- 입력값이 유한대로 향할때 함수의 상한을 설명하는 수학적 표기 방법
- 점근적 실행 시간(Asymptotic Running Time) 표기에 사용
 

점근적 실행 시간이란?

- 입력값 n이 커질 때, 극한 함수의 실행 시간의 추이를 의미
- 시간 복잡도라고도 함 ( 어떤 알고리즘을 수행하는 데 걸리는 시간을 설명하는 계산 복잡도)
 

빅오 표기법의 종류

-O(1) : 입력값이 아무리 커도 실행 시간은 일정
-O(log n) : 이진 검색이 이 경우에 해당하는데, 입력값에 영향을 받으나, log 함수의 특성 상 크게 영향을 받지 않는 편
-O(n) : 선형 시간 알고리즘. 입력값만큼 실행 시간에 영향을 받으며, 알고리즘을 수행하는 데 걸리는 시간은 입력값에 비례함.
-O(n log n) : 효율이 좋은 알고리즘이 해당. 매우 빠름.
-O(n^2) : 버블 정렬과 같은 비효율 알고리즘이 이에 해당.
-O(2^n) : 재귀적 알고리즘이 해당. 참고로 n^2보다 더 큼.
-O(n!) : 가장 느린 알고리즘. 입력값이 조금만 커져도 웬만한 시간 내에는 계산이 어려움.
 

상한과 최악

-빅오 : 상한(Upper Bound) 의미
-빅오메가 : 하한(Lower Bound) 의미
-빅세타 : 평균 의미
 

분할 상환 / 상각

- 최악의 경우를 여러 번에 걸쳐 골고루 나눠주는 형태로 알고리즘의 시간 복잡도 계산
 

---

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