[알고리즘] 빅오 표기법

빅오$(Big-Oh)$ 표기법은 알고리즘이 시간적으로 얼마나 효율적인지를 분석하기 위한 표기법이다.

 

알고리즘 성능의 기준으로는

1. 연산량$(시간복잡도)$

2. 메모리 사용량$(공간복잡도)$

을 들 수 있다.

 

이 중 수행 시간과 연관이 있어 알고리즘이 최대로 오래 걸릴 때 얼마나 걸리는지를 표현하는 방법이 빅오 표기법이다.

 

빅오 표기법은 아래와 같이 표현된다.

 

1. 주어진 수행시간의 다항식에 대해 다항식에서 최고차 항만을 취한다.

 

2. 해당 최고차 항의 계수를 제거한다.

 

예를 들어, 알고리즘의 최대 수행시간을 아래와 같은 다항식으로 나타냈다고 했을 때,

 

2(N^{2}) + 3N + 5

 

1과 2의 과정을 거치면 (N^{2}) 이 된다.

 

O$(N^{2})$가 바로 빅오 표기법으로 표기한 알고리즘의 시간복잡도가 된다.