[자료구조] 1.2 알고리즘의 성능분석 방법 (5)

알고리즘의 성능분석 방법 (5)

빅-오 표기법 (Big-Oh Notation | Big-Θ 표기법)

빅-오 표기법의 정리

• 함수 T(n)에서 시간 복잡도의 측정에 영향을 주지 않는 부분을 생략하고 영향력을 끼치는 부분만 남긴다
• 함수 T(n)가 다항식일 때, 최고차항의 차수가 생략되지 않는다.
• 최고 차항의 차수 = 빅-오

빅-오 그래프

O(1)
상수시간 이내에 실행.
상수의 값이 너무 크지만 않다면 투입 값과 관계없이 일정한 실행시간을 가지는 최선의 알고리즘.

O(log n)
투입값의 크기에 따른 영향을 비교적으로 적게 받는다.
대표적으로는 이진 탐색 알고리즘이 있다.

O(n)
투입값의 크기에 비례하여 수행 시간도 결정되는 알고리즘.

O (n log n)
효율적인 알고리즘.
퀵 정렬, 합병 정렬, 힙 정렬 등 알고리즘이 포함된다.

O(n^2)
이차 시간.
투입 값의 크기에 제곱만큼 수행 시간이 필요하다. 버블 정렬, 선택 정렬, 삽입 정렬이 대표적이다.

O(2^n)
지수 시간.
투입값으로 만들 수 있는 부분 집합 경우의 수를 모두 생성한다.
투입값의 크기 변화에 비해 급격한 수행 시간 증가를 가지는 알고리즘. 효율이 떨어지기 때문에 사용하기 힘들다.

O(n!)
계승 시간.
비효율적인 알고리즘으로 실제 사용이 힘들다.

참고

• 윤성우의 열혈 자료구조
  
• 윤성우의 열혈 자료구조 강의