Big-O 표기법이란?

수리과학의 여러 분야에서 함수의 증감 추세를 비교하는 표기법이다. 컴퓨터 과학에서는 일반적으로 알고리즘의 시간복잡도를 나타내는데 사용된다.

Big-O표기법을 쓰는 이유

프로그램이 돌아가는 정확한 표기법을 결정하는 작업은 매우 어려우며, 난해하여 직관적이지 않기 때문에 이것을 간략하게 표기하기 위해 사용한다.

예를 들어, 어떤 프로그램이 10억개의 단계를 밟는다고 할 때, 이 숫자는 직관적이지도 않고 아무도 관심있어하지 않는다. 이를 대략적으로 'n에 비례한다'라고 표현하여 직관성을 높인 것이 Big-O표기법이라고 할 수 있다.

우리는 위 그래프를 통해 '입력 값이 커질 수록 선형적으로 소요시간이 증가한다.'라는 것을 직관적으로 알 수 있다. 이를 Big-O 표기법으로 O(n)이라고 표기한다.

결론적으로, Big-O표기법은 파일의 크기에 따른 소요시간을 대략적으로 그리고 수학적으로 표현한 표현 방법이다. 이 Big-O표기법을 이용하여 프로그램의 시간복잡도(Time Complexity)표현하는데 사용된다. 이 시간복잡도를 이용하여 우리가 공부하는 알고리즘의 대략적인 성능을 파악할 수 있다.

다음 포스팅을 통해 이 시간복잡도의 기본적인 종류들에 대해 알아보자.