big-O 표기법

big-O

big-O 표기법이란 알고리즘의 효율성을 판단하기 위한 척도이다. big-O는 간단히 말하자면 n이라는 입력값이 무한히 커질 경우 실행시간의 추이를 나타낸다. 따라서 충분히 큰 입력값이 주어졌을 때 알고리즘의 효율성에 따라 수행 시간이 크게 차이가 난다.

시간 복잡도

얼마나 수행 시간이 필요한가, 연산 횟수가 얼마나 되는가를 기준으로 판단하는 것이 시간복잡도이며 이 시간복잡도를 표현하는데 big-O 표기법을 이용한다.

분류와 성능순 정렬

분류

• O(1): 상수형 알고리즘. 데이터 입력량과는 무관하게 실행 시간이 일정하다.
• O(n): 선형 알고리즘. 데이터 입력량에 비례해 실행 시간이 늘어난다.
• O(log n): 로그형 알고리즘. 시간이 선형적으로 증가하면 n이 기하급수적으로 증가한다. 데이터 입력량이 늘어날수록 단위 입력당 실행시간이 줄어든다.
• O(n log n): 선형 - 로그형 알고리즘. 데이터 입력량이 n배 늘어나면 실행 시간이 n배 조금 넘게 늘어난다.
• O(n^2): 2차 알고리즘. 데이터 입력량의 제곱과 비례하여 실행 시간이 늘어난다.
• O(2^n): 지수형 알고리즘. 데이터 입력이 추가될 때마다 실행 시간이 2배로 늘어난다.
• O(n!): 팩토리얼(계승)형 알고리즘. 데이터 입력이 추가될 때마다 실행시간이 n배로 늘어난다.

성능순 정렬

알고리즘 성능은 좋은 순서대로 다음과 같다.

• O(1), O(log n), O(n), O(n log n), O(n^2), O(2^n), O(n!)

성능별 대표적인 알고리즘

• O(log n): 기수 정렬
• O(n log n): 힙 정렬, 병합 정렬
  • 퀵 정렬 (최선: n log n / 최악: O(n^2))
• O(n^2): 버블 정렬, 선택 정렬

이진 검색의 경우

데이터가 커질수록 단계 수가 늘어나므로 이진 검색은 O(1)이라 표현할 수 없다.
그러나 검색하고 있는 배열의 원소 수보다 단계 수가 훨씬 적으므로 O(N)이라 표현할 수도 없다.

이진 검색은 O(1)과 O(N)사이에 있으므로 이것을 big-O 표기법에선 O(log n)으로 나타낸다.