본문 바로가기

컴퓨터 공학/알고리즘

[컴퓨터 알고리즘 성능분석] 점근적 표기법 (Asymptotic Notation)


[컴퓨터 알고리즘 성능분석] 점근적 표기법 (Asymptotic Notation)


점근적 분석

주어진 문제를 푸는 알고리즘은 딱 하나만 있는 것이 아니라 여러 개가 존재한다.

하드웨어, 운영체제, 프로그래밍 언어 등 특징에 따라서 최적화된 여러가지 알고리즘이 존재한다.

어떤 문제를 해결하는 데에는 항상 다수 개의 알고리즘이 존재할 수 있으므로 알고리즘의 성능을 비교할 필요가 있다.


점근적 분석의 필요성

어떠한 문제 해결을 위한 알고리즘의 성능분석을 할 때, 주어지는 데이터의 형태나 실험을 수행하는 환경, 또는 실험에 사용한 시스템의 성능등 다양한 요소에 의해 공평한 결과가 나오기 힘들고 비교 결과가 항상 일정하지 않을 수 있다.

이를 효과적으로 해결하는 방법이 점근적 분석법이다. 점근적 분석법은 각 알고리즘이 주어진 데이터의 크기를 기준으로 수행시간 혹은 사용공간이 얼마나 되는지를 객관적으로 비교할 수 있는 기준을 제시해 준다. O(빅오), Ω(오메가), Θ(세타)등이 있다. 일반적으로 빅오와 세타표기가 많이 사용된다.


O Notation (빅오 표기법)

- 점근적 상한선(Asymptotic upper bound)

- 주어진 알고리즘이 아무리 나빠도 비교하는 함수와 같거나 좋다.

- 정의 : O(g(n)) = {f(n) : there exist positive constants and $ n_0 $ such that 0≤f(n)cg(n) for all n≥$ n_0 $}


$n_0$를 기준으로 $n_0$보다 오른쪽에 있는 모든 n 값에 대해 함수 $f(n)$은 함수 $cg(n)$보다 작거나 같다는 의미이다. 그래프가 아래에 있을 수록 수행시간이 짧은 것이므로 성능이 좋은 것이다.


 Notation (오메가 표기법)

- 점근적 하한선(Asymptotic lower bound)

- 주어진 알고리즘이 아무리 좋아도 비교하는 함수와 같거나 나쁘다.

- 정의 : (g(n)) = {f(n) : there exist positive constants and $ n_0 $ such that 0≤cg(n)f(n) for all n≥$ n_0 $}


$n_0$를 기준으로 $n_0$보다 오른쪽에 있는 모든 n 값에 대해 함수 $f(n)$은 함수 $cg(n)$보다 크거나 같다는 의미이다. 


Θ Notation (세타 표기법)

- 점근선 상한선과 점근적 하한선의 교집합(Asymptotic tighter bound)

- 주어진 알고리즘이 아무리 좋아지거나 나빠지더라도 비교하는 함수의 범위안에 있다.

- 정의 : Θ(g(n)) = {f(n) : there exist positive constants $c_1$, $c_2$ and $ n_0 $ such that 0≤$c_1 g(n)$f(n)≤$c_2 g(n)$ for all n≥$ n_0 $}


$n_0$를 기준으로 $n_0$보다 오른쪽에 있는 모든 n 값에 대해 함수 $f(n)$은 함수 $c_1 g(n)$보다 크거나 같거나 $c_2 g(n)$보다 작거나 같다는 의미이다.


성능비교의 대상

컴퓨터 알고리즘 성능 비교 대상을 여러가지가 있지만 크게 세 가지로 본다.

- 산술 연산 (Arithmetic Calculation)

- 데이터 이동 연산 (Data movement)

- 제어 연산 (Control)

일반적으로 비교연산이나 곰셈연산 혹은 모듈러연산등 알고리즘에서 가장 중점적으로 사용하는 연산을 성능비교의 대상으로 한다.


  • ㅋㅋㅋ 2015.12.29 03:19 댓글주소 수정/삭제 댓글쓰기

    성능 분석을 할 때, 기존의 방법이 먹히지 않는 경우가 종종 생깁니다. Computation이 바로 반영 안되는 알고리즘의 경우가 이렇죠. 이럴 경우는 Amortized Time으로 계산하시고 이건 Worst Case Time Complexity에 bound하니 계산된 Amortized Time을 Worst Case Time으로 보시면 됩니다.