Reference

• 박상길, 파이썬 알고리즘 인터뷰

1. 빅오(O, big-O)

빅오(O, big-O): 입력값이 무한대로 향할 때 함수의 상한을 설명하는 수학적 표기 방법
-Reference. Big O notation, Wikipedia

1.1. 시간 복잡도(Time Complexity)

시간 복잡도(Time Complexity): 알고리즘을 수행하는 데 걸리는 시간을 설명하는 계산 복잡도(Computational Complexity). 계산 복잡도를 표기하는 대표적인 방법이 빅오이며 빅오로 시간 복잡도를 표현할 때는 최고차항만을 표기하며 계수는 무시함.
-Reference. Time Complexity, Wikipedia

1.1.1. 빅오 표기법의 종류

• $O(1)$: 입력값이 아무리 커도 실행 시간이 일정. 해시 테이블의 조회 및 삽입.

• $O(log n)$: 로그는 매우 큰 입력값에도 크게 영향을 받지 않아 매우 견고함. 이진 검색.

• $O(n)$: 입력값만큼 실행 시간에 영향을 받으므로 알고리즘을 수행하는 데 걸리는 시간은 입력값에 비례. 선형시간(Linear-Time) 알고리즘. 정렬되지 않은 리스트에서 최댓값 또는 최솟값을 찾는 경우.

• $O(n log n)$: 대부분의 효율 좋은 정렬 알고리즘. 병합 정렬. $O(n)$ 알고리즘은 아무리 좋은 알고리즘이라도 $O(n log n)$보다 빠를 수 없음. 팀소트(Timsort)는 입력값이 최선인 경우 $O(n)$.

• $O(n^2)$: 비효율적인 알고리즘. 버블 정렬.

• $O(2^n)$: 피보나치 수를 재귀로 계산하는 알고리즘. $O(n^2)$ < $O(2^n)$(시간 복잡도)

• $O(n!)$: 외판원 문제(TSP, Travelling Salesman Problem)를 브루트 포스로 풀이하는 경우. 입력값이 조금만 커져도 왠만한 다항 시간(선형 시간: $O(n)$, 제곱 시간: $O(n^2)$, 세제곱 시간: $O(n^3)$) 내에는 계산이 어려움.

1.1.2. 시간과 공간의 트레이드오프(Space-Time Tradeoff)

메모리를 많이 사용할수록 시간 복잡도를 더 적게할 수 있지만 비용이 증가.
메모리를 적게 사용할수록 비용이 줄지만 시간 복잡도가 더 증가.
따라서, 시간과 공간의 타협점을 잘 찾아야 함.

1.1.3. 상한과 최악

• 빅오($O$): 상한(Upper Bound)
• 빅오메가($\Omega$): 하한(Lower Bound)
• 빅세타($\Theta$): 평균

빅오 표기법은 주어진(최선/최악/평균) 경우의 수행시간의 상한을 나타냄. (상한 $\ne$ 최악)
-Reference. 대문자 O 표기법과 퀵 정렬의 시간 복잡도