| 알고리즘의 분석 기준 | 점근적인 복잡도 평가 |
점근적인 복잡도 평가
■ O-표기법(order notation, O-notation, big oh notation)
데이터 수 n에 대해서 복잡도가 어떠한 함수로 나타나는가를 간단히 표현하기 위한 알고리즘 표현법
■ 점근적인 복잡도 표기법을 이용한 알고리즘의 복잡도
O(1)
O(logN)
O(N)
O(NlogN)
O(N2)
O(N3)
O(2n)
상수형, 입력 크기와 무관하게 바로 해를 구함. 해슁
로그형, 입력 자료를 나누어 그 중 하나만 처리
선형, 입력 자료를 차례로 하나씩 모두 처리
분할과 합병형, 자료를 분할하여 각각 처리하고 합병
제곱형, 주요처리(기본연산) loop 구조가 2중인 경우
세제곱형, 주요처리(기본연산) loop 구조가 3중 경우
지수형, 가능한 해결방법 모두를 다 검사하며 처리함
