점근적 표기

점근적 표기

알고리즘은 입력 크기가 아주 작으면 알고리즘의 효율성에 상관없이 금방 끝난다. 알고리즘의 효율성이 문제가 되는 것은 입력의 크기가 충분히 클 때이다. 그래서 알고리즘의 수행시간을 분석할 때는 항상 입력의 크기가 충분히 클 때에 대해서 분석한다. 즉, 점근적 분석을 한다.

점근적 분석의 필요성

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

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

O Notation (빅오 표기법)

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

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

알고리즘의 소요시간이 입력의 크기 n에 대해 O(n^2)이라면 기껏해야 n^2에 비례하는 시간이 소요됨을 뜻한다. 다시 말해, O(f(n))은 점근적 증가율이 f(n)을 넘지 않는 모든 함수들의 집합이다. 예를 들어, n^2 + 3 과 3n^2 + 5, n + 4, 2nlog n + 3n 등은 모두 O(n^2)이다. 그래서 빅오 표기법은 점근적 상한이라고 한다.

Ω Notation (빅오메가 표기법)

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

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

알고리즘의 소요시간이 입력의 크기 n에 대해 Ω(n)이라면, 적어도 n에 비례하는 시간이 소요됨을 뜻한다. Ω(f(n)) 은 점근적 증가율이 적어도 f(n)이 되는 모든 함수들의 집합이다. 따라서, 5n^2, 3n^2, 5n^3, 4n^4 + 23, 2n^6 - 7n 은 모두 Ω(n^2)이라고 할 수 있다. 그래서 빅오메가 표기법을 점근적 하한이라고 한다.

Θ Notation (세타 표기법)

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

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

알고리즘의 소요시간이 입력의 크기 n에 대해 Θ(n)이라면, 대략 n에 비례하는 시간이 소요됨을 뜻한다. Θ(f(n)) 은 점근적 증가율이 대략 f(n)이 되는 모든 함수들의 집합이다. 따라서, 5n, 3n, 5n - 3, 4n + 4, 2n - 7n 은 모두 Θ(n)이라고 할 수 있다.

o 표기법 (스몰오 표기법)

- 점근적 상한 중에서 여유있는 상한

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

o 표기는 함수의 증가율이 점근적 의미에서 어느 한계보다 더 작다는 것을 표현하고자 할 때 사용한다. 예를 들어, 함수 5n, 5n + 3, 2n + 7 등은 o(n^2)이다. 왜냐하면 저 함수들의 증가율은 n^2보다 작기 때문이다. 이러한 스몰오 표기법을 여유있는 상한이라고 한다.

ω 표기법 (스몰오메가 표기법)

- 점근적 하한 중에서 여유있는 하한

- 주어진 알고리즘이 아무리 좋아도 비교하는 함수보다 좋지 못하다

ω 표기는 o 표기와 정확히 대조되는 표기이다. ω 표기는 함수의 증가율이 점근적 의미에서 어느 한계보다 더 크다는 것을 표현하고자 할 때 사용한다. 예를 들어, 함수 5n^3 은 ω(n^2) 이라고 할 수 있다. 5n^3의 증가율이 n^2의 증가율보다 더 크기 때문이다. 이러한 ω 표기를 여유있는 하한이라고 한다.