[자료구조] 빅 오 표기법

  서로 간에 시간 복잡도를 쉽게 소통할 목적으로 자료 구조와 알고리즘의 효율성을 간결하고 일관된 언어로 설명하기 위해 수학적 개념을 차용했는데 이 개념을 형식화한 것이 빅 오 표기법이다. 빅 오 표기법은 알고리즘의 효율성을 쉽게 분류하고 이해시킬 수 있는 장점이 있다.

 

  빅 오는 시간 단위가 아닌 알고리즘에 필요한 단계 수만을 고려함으로써 일관성을 유지한다. 1 단계만 필요한 알고리즘은 다음과 같이 표기한다.

 

O (1)

 

  일반적으로 "빅 오 1"이라고 발음한다. "차수 1"이라고도 한다. O (1)은 데이터의 크기에 상관없이 알고리즘에 필요한 단계 수가 일정하다는 의미다. 배열에 N개의 원소가 있을 때 선형 검색은 최대 N단계가 걸리는데 빅 오 표기법으로는 다음과 같다.

 

O (N)

---

상수 시간과 선형 시간

  O(N)으로 표기한 알고리즘은 배열에 추가되는 원소에 따라 변화되는 그래프를 그릴 수 있다. O(1) 알고리즘은 항상 같은 단계 수를 가지기 때문에 가로로 길게 늘어서게 된다.

  O(N)은 완벽한 대각선을 그린다. 선형 검색 알고리즘이 이에 해당한다. O(N)은 선형 시간(linear time)이라고 부른다. 이와 다르게 O(1)은 완벽한 수평선을 그린다. 이는 데이터가 얼마나 많든 상관없이 알고리즘에 걸리는 단계 수가 항상 일정하기 대문이다. O(1)은 상수 시간(constant time)이라고 부른다.

 

  빅 오는 본래 데이터 양이 변할 때 알고리즘의 성능이 어떻게 변하는가를 설명하므로 그래프 사이의 성능을 비교하는 것은 중요하다.