Big O Notation

빅 오 표기법

대부분의 사람들이 알고리즘 공부를 시작할 때 Big O Notation, 빅 오 표기법이라는 개념을 접하게 된다.

컴퓨터 과학에서의 빅 오 표기법은 일반적으로 알고리즘의 시간복잡도를 나타내는데 사용된다.

시간복잡도란 컴퓨터 프로그램의 입력값과 연산 수행 시간의 상관관계를 나타내는 척도이다.

(* 공간복잡도의 이론적인 상한은 시간복잡도이기 때문에 보통은 시간복잡도가 좀 더 중요하게 취급된다.)

쉽게 이야기 하면 입력값의 개수가 늘어날 때 출력까지 걸리는 시간이 얼마나 되느냐를 함수 혹은 그래프 형태로 나타내는 표기법이라고 할 수 있다.

빅 오 표기법과 같은 시간, 공간복잡도 측정 기법이 생겨난 배경은 알고리즘의 성능을 측정하기 위해서다.

일반적으로 하나의 알고리즘 문제에서 해답이 될 수 있는 코드는 적으면 몇개에서 많게는 몇백, 몇천개까지도 존재한다.

입력값이 작다면 그러한 코드들의 알고리즘 수행 시간이 별로 차이가 나지 않을 수 있지만, 입력값이 커질수록 극적인 차이가 나게되는 경우가 생긴다.

우리는 이러한 코드들 중에서 가장 빠르거나 가장 메모리를 적게 사용하는 몇 가지의 코드만 원하기 때문에 시간복잡도, 공간복잡도를 측정하여 최적의 코드를 알아낼 수 있다.

항상 하나의 최적 코드가 존재하는 것은 아니고 최적에 가까운 여러 코드들 중에서 상황에 적합한 코드를 찾으면된다.

공간복잡도의 상한이 시간복잡도에 맞춰져 있기 때문에 일반적으로 알고리즘의 성능을 측정할 때 시간복잡도에 초점을 맞춘다.

입력값을 n이라고 할 때 출력에 걸리는 시간을 대문자 O와 소괄호 사이에 넣는다.

여기서 빅오 표기법의 특징이 있는데 첫번째로 상수항을 무시하고, 두번째로는 영향력이 없는 항을 무시한다는 것이다.

입력값에 영향을 받는 항 중에서 지수가 가장 큰 항만 남기고 다른 항은 무시한다. 지수가 가장 큰 항의 상수항 역시 무시한다.

일반적으로 입력값 n에 영향을 받지 않는 O(1)이 가장 빠르고, 오른쪽으로 갈 수록 느려진다.

왼쪽으로 갈수록 평균적으로 빨라지지만 항상 왼쪽의 알고리즘이 빠른것은 아니다.

예를 들면 정렬 알고리즘에서 시간복잡도 O(n^2)인 버블정렬과 시간복잡도 O(nlogn)인 퀵정렬을 수행할 때, 정렬할 요소의 초기 상태에 따라 버블정렬이 퀵정렬보다 빠른 경우도 존재한다.

하지만 대부분의 경우는 퀵정렬의 속도가 빠르기 때문에 우리는 일반적으로 코드의 성능을 비교할 때는 평균적인 수행시간을 나타내는 시간복잡도를 비교하여 평가한다.

입력값이 적을 때는 시간복잡도가 크게 의미가 없는 경우도 있지만, 입력값이 커질수록 유의미한 효과를 나타낸다고 볼 수 있다.

- 나무위키 : 시간 복잡도, 점근 표기법