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

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

점근적 분석

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

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

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

점근적 분석의 필요성

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

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

O Notation (빅오 표기법)

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

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

- 정의 : O(g(n)) = {f(n) : there exist positive constants c 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 c 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)

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