복잡도란 알고리즘의 성능을 평가하는 척도로 시간 복잡도와 공간 복잡도로 나뉜다.
- 시간 복잡도(Time Complexity): 알고리즘을 수행하는 데 이루어지는 연산의 양
- 공간 복잡도(Space Complexity): 알고리즘을 수행하는 데 필요로 하는 자원의 양
알고리즘의 성능은 주어지는 데이터의 형태나 실험을 수행하는 환경, 또는 실험에 사용한 시스템의 성능 등 다양한 요소에 의해 공평한 결과가 나오기 힘들고 비교 결과가 항상 일정하지 않을 수 있다.
이를 주어진 데이터의 크기를 기준으로 비교할 수 있게 만든 것이 점근적 분석법이다.
- O Notation (빅오 표기법): 점근적 상한선 / 최악의 경우
- Ω Notation (오메가 표기법): 점근적 하한선 / 최상의 경우
- θ Notation (세타 표기법): 점근적 상한선과 점근적 하한선의 교집합 / 평균의 경우
