빅오(Big-O)표기법에 대해 알아보자

빅오(Big-O)표기법이란?

앞서 설명한 복잡도를 표현하는 표기법으로 빅오(Big-O)을 사용한다. 빅오(Big-O) 표기법은 알고리즘의 시간 복잡도와 공간 복잡도를 표현하기 위한 수학적인 표기법이다.

표기방법

알고리즘의 시간 복잡도와 공간 복잡도는 입력의 크기에 따라 변화한다.

예를 들어, 배열의 길이가 10인 경우와 1000인 경우에 동일한 알고리즘을 실행한다면 실행 시간은 차이가 날 것이다. 빅오(Big-O) 표기법은 이러한 차이를 표현하기 위해 입력의 크기 n에 따른 알고리즘의 실행 시간 T(n)이나 공간 복잡도 S(n)을 대략적으로 나타내는 표기법이다.

빅오(Big-O) 표기법은 O( ) 안에 실행 시간 T(n)이나 공간 복잡도 S(n)을 나타내며, 입력의 크기 n에 따른 함수의 상한선을 의미한다. 이때 O( ) 안에 들어가는 함수는 가장 큰 차수를 나타내는 항만 표시한다.

예를 들면, O(n^2)은 n이 증가함에 따라 알고리즘의 실행 시간이 제곱만큼 증가한다는 것을 의미한다.

일반적으로 알고리즘의 시간 복잡도와 공간 복잡도를 나타내는 빅오(Big-O) 표기법은 아래와 같다.

O(1) : 상수 시간/공간 알고리즘
O(log n) : 로그 시간/공간 알고리즘
O(n) : 선형 시간/공간 알고리즘
O(n log n) : 선형 로그 시간/공간 알고리즘
O(n^2) : 이차 시간/공간 알고리즘
O(2^n) : 지수 시간/공간 알고리즘