[Chapter 2] 쉽게 배우는 알고리즘[점근적 표기]

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

즉, 점근적 분석을 한다.

를 이용한 분석이 점근적 분석의 한 예시이다.
변수의 크기가 충분히 큰 경우 변수가 커짐에 따라 함수가 증가하는 비율을 표현하는 방법이다. 이를 함수의 점근적 증가율이라고 하고, 그 표기법을 점근적 표기법이라 한다.

고등학교에서 배우는 무한의 개념을 사용하면이다.

 

이것은 함수 >은 n이 충분히 커짐에 따라 2n+3의 비율로 증가한다는 뜻이다.

점근적 표기법은 이를 좀 더 간명화한다. 이들 중 O-표기법을 사용하면이다.

이것은 함수>은 n이 충분히 커짐에 따라 n에 대한 일차식의 비율로 증가한다는 뜻이다.

표기법에서는 함수의 차수와 계수를 다 중시하지만, 표기법에서 계수는 중요하지 않다.

여러 함수의 증가율 비교

n이 작을 때는 차이가 그리 크지 않지만 n이 커짐에 따라 차이는 극적으로 벌어진다.

n이 작을 때는 함수의 앞에 붙은 계수가 두 함수의 차이에 영향을 많이 주지만, n이 커짐에 따라 그 차이에 비해 영향이 미미하다. 점근적 표기에서 계수를 무시하는 것은 이런 이유 때문이다.

알고리즘을 분석하려고 입력의 크기를 무엇을 잡을지는 대부분 명확하다. 여러 수를 크기 순으로 정렬하는 알고리즘이면 정렬하고자 하는 수의 개수가 입력의 크기가 된다. 그리고 그래프 알고리즘에서는 대부분 정점의 개수와 간선의 개수 둘을 입력의 크기로 사용한다.

앞으로 취급하는 모든 함수는 양의 값을 갖는다고 가정한다. 알고리즘의 소요 시간이나 자원의 소모량을 표현하는 함수이므로 음의 시간은 의미 없기 떄문이다.

알고리즘의 분석에 사용하는 대표적인 세 가지 점근적 표기법

Θ - 표기법

알고리즘의 소요 시간이 입력의 크기 n에 대해 Θ(n^2)이라면(세타라고 읽는다.) 대략 n^2에 비례하는 시간이 소요됨을 뜻한다.

은 점근적 증가율이 과 일치하는 모든 함수의 집합이다.

Θ-표기는 집합으로 정의되므로 으로 쓰는 것이 맞지만 보통 으로 쓴다.

따라서 에서 = 는 의 대신이므로 과 같이 표현하면 안된다. >이 아니기 때문이다. O,표기법 모두 집합으로 정의되며, 모두 대신 = 를 사용한다.

ex)정렬 알고리즘의 예시 : 버블 정렬의 수행시간은 >이고, 병합 정렬의 수행 시간은 이다.

O-표기법

알고리즘의 소요 시간이 입력의 크기 n에 대해 이라면 n^2에 비례하는 시간이 소요됨을 뜻한다.

은 점근적 증가율이을 넘지 않는 모든 함수의 집합이다.

은 최고차항의 차수가 과 일치하거나 더 작은 함수의 집합이다. O-표기는 함수의 점근적 상한을 나타낸다

O-표기의 수학적 정의는 다음과 같다.

정의 : O( g(n) ) = { f(n) | ∃ c > 0, n₀ ≥ 0 s.t. ∀ n ≥ n₀, cg(n) ≥ f(n) } → 증명 수식

Ω -표기법

알고리즘의 소요 시간이 입력의 크기 n에 대해 이라면 적어도 n^2 에 비례하는 시간이 소요됨을 뜻한다.

 

은 점근적 증가율이 적어도 이 되는 모든 함수의 집합이다.

 

은 최고차항의 차수가 과 일치하거나 더 큰 함수의 집합이다.

-표기는 함수의 점근적 하한을 나타낸다.

-표기의 수학적 정의는 다음과 같다.

s.t는 such that의 준말로 A s.t B는 "B를 만족하는 A"라는 뜻이다.

그리고 O-표기와 -표기의 정의를 이용해 -표기를 다음과 같이 정의할 수 있다.

즉, 은 과

에 모두 속하는 함수의 집합이다.<

---

Reference

쉽게 배우는 알고리즘

https://hcr3066.tistory.com/175

02. 알고리즘 설계와 분석 2 - 점근적 표기법