빅오 표기법 (Big-O Notation, 점근 표기법)

빅오 표기법 (Big-O notation, 점근 표기법)은 소프트웨어 엔지니어링, 특히 데이터 엔지니어링에 있어서 알고 있어야 할 필수 요소이다.

빅오 표기법은 함수처럼 표기할 수 있다. 수학적 연산 시간이 주어진 입력 자료에 관계 없이 일정할 때에는 "상수 시간"이라고 부르며, O(1) 라고 표기할 수 있다. 예를 들면 (1) 주어진 키를 이용해 해시맵 내의 자료에 접근하거나, (2) 주어진 인덱스 값을 이용하여 배열 내의 원소에 접근한다던가, 혹은 (3) 연결 리스트 중에서 다음 원소로 넘어가는 연산들의 경우에는, O(1) 상수 시간으로 처리할 수 있다.

상수 시간으로 처리할 수 없는 연산의 경우, 대개 주어진 입력 자료의 크기에 비례하기 마련이다. 예를 들어, 주어진 숫자 배열이 있고 그 배열의 크기를 n 이라고 가정했을 때, 최대 값을 찾아내기 위해서는 각 원소들을 한번씩 훑어보아야 하기 때문에 O(n) 만큼의 연산 시간이 소요된다고 볼 수 있다.

배열에 for 문을 사용하는 경우의 대부분은 O(n) 연산이라고 할 수 있다. 필요한 원소가 배열 안에 있는지 확인하기 위해서는 O(n) 의 연산 시간이 필요하다. 해시맵 혹은 집합 자료구조의 경우 같은 연산을 처리하는 데에는 O(1) 의 연산 시간이 필요하다.

연산 시간 복잡도를 가장 빠른 것 부터 순서대로 나열하자면 다음과 같다:

O(1) < O(log n) < O(n) < O(n*log n) < O(n^2) < O(n!) < O(n^n)

처리해야 할 자료의 크기가 점점 커짐에 따라 각 알고리즘별로 다양하게 연산 시간이 커지게 된다. 예를 들어 자료의 크기 n 이 10 보다 작다면, 어떠한 복잡도를 가진 알고리즘을 쓰게 되더라도 결국 비슷한 결과가 나오기 마련이다. 하지만 n 이 수천, 수만, 또는 수백만으로 늘어나게 된다면 상대적으로 연산 시간이 오래 걸리는 알고리즘들은 조금이라도 빠른 알고리즘에 비해 엄청나게 오랜 시간/공간이 소요된다고 볼 수 있다.

가령, 하나의 연산을 수행하는 데 1초의 시간이 걸린다고 가정한다면, 주어진 자료의 크기가 10개라면 (n = 10), O(n)의 경우 10초, O(log n) 의 경우 1초 걸린다고 생각할 수 있다. 9초 차이 정도야 아무 것도 아니라고 생각할 수 있겠지만, 자료의 크기가 1000개로 늘어나게 된다면 (n = 1000), O(n)의 경우 1000초, O(log n)의 경우 3초밖에 걸리지 않게 된다! 997초동안 컴퓨터에게 얼마나 효율적인 일을 시킬 수 있는지 상상한다면 엄청나게 큰 차이가 되기 마련이다.

이렇게 각 자료구조 및 알고리즘들의 특성들을 이용해 코드를 짜면 더 효율적으로 필요한 처리를 할 수 있다.