복잡도 표기법

알고리즘을 분석하는 방법은 시간 복잡도와 공간 복잡도로 나뉜다.

- 시간 복잡도 (time complexity) : 알고리즘이 완료되는데까지 소요되는 시간

- 공간 복잡도 (space complexity) : 알고리즘이 완료되는데까지 필요한 메모리 공간

이러한 복잡도의 표기방법으로는 총 3가지가 존재한다.

1. 빅오메가(Big-Omega)

2. 빅세타(Big-Theta)

3. 빅오(Big-O)

이 표기법들을 점근적 표기법 즉 대략적인 표기법이라고 한다.

n을 알고리즘의 input의 크기라고 할 때.

알고리즘의 복잡한 함수를 일일이 나타내지 않고, 알고리즘의 basic operation을 선택해 basic operation의 수를 n에 대한 비례식으로 세우는 것이다. (중요하지 않은 항과 상수 계수를 제거)

각 표기방법에 대해 자세히 알아보자.

빅오메가(Big-Omega)

- 정의 (함수f와 g가 있을 때)

- 알고리즘이 상한선 없이 최소한 어느 정도 걸린다고 알아야 할때 사용

- 점근적 하한, 혹은 최선의 경우라고 한다.

빅세타(Big-Theta)

- 정의 (함수f와 g가 있을 때)

- 점근적 상한 & 하한, 즉 점근적 평균

- 빅오메가와 빅오의 교집합 부분이다.

빅오(Big-O)

- 정의 (함수f와 g가 있을 때)

- 점근적 상한, 혹은 최악의 경우라고 한다.

- 최악의 경우니깐 이보다도 빠를 수 있다는 뜻이이다.

- 가장 일반적으로 사용된다.

3가지 표기법의 관계를 그래프로 표현하면 이러하다

(표기법 예시)

---

(참고) input n에 함수의 크기는 이러하다.