[디딤돌 자료구조와 알고리즘 with C] 1.3 알고리즘의 평가와 접근적 표기

1.3 알고리즘의 평가와 접근적 표기

같은 문제를 해결하는 알고리즘은 여러 개가 있을 수 있죠. 전산에서 알고리즘을 평가하는 방법은 여러가지가 있어요. 그 중에서 수행 속도를 평가하거나 메모리 효율을 평가하는 점근식 방법을 많이 사용하죠.

 

점근적 표기에서는 n개의 자료가 있을 때 알고리즘 수행 시간(혹은 메모리 사용)이 n과 어떠한 상관관계가 있는지 표현하는 방법입니다.

 

예를 들어 어떠한 알고리즘이 n개의 자료가 있을 때 수행 시간 T(n)= 3n+27이라고 가정할게요.

 

만약 n이 충분히 큰 수라면 가장 높은 차수의 항이 결과에 가장 큰 영향을 주겠죠. 점근식 표기에서는 가장 높은 차수의 항을 제외한 나머지 차수의 항은 버리고 계산해요. 그리고 상수도 생략하여 평가합니다. 따라서 T(n)=3n+27과 같은 수행 시간을 가질 때 점근식으로 말할 때는 n에 비례한다고 말해요.

 

점근적 표기에는 Θ(세타, 점근적 평균), O(빅 오, 점근적 상한: 최악의 경우를 말함), Ω(오메가, 점근적 하한: 최선의 경우를 말함)을 많이 사용하며 o(리틀 오, 여유있는 상한: 보다 엄격한 최악의 경우), ω(리틀 오메가, 여유있는 하한: 보다 엄격한 최선의 경우)도 있어요.

 

이들 중에 전산에서는 점근적 평균인 Θ(세타)와 점근적 상한인 O(빅 오)를 많이 사용하며 특히 최악일 때도 이 정도의 성능은 나온다고 얘기하기 위해 O(빅 오)를 가장 많이 사용합니다.

 

이 책에서도 일부 알고리즘의 성능을 평가하는 방법을 보여줄 것이며 대부분 O(빅 오) 표기를 이용하여 평가할 것입니다.

 

1.3.1  Θ(세타)

Θ 표기는 점근적으로 평균을 표현하는 표기입니다. n이 특정 수보다 클 때의 평균을 의미합니다. 어떤 알고리즘이 f(n)일 때 다음과 같은 수식으로 표현할 수 있으면 접근적 표기에서는 g(n)이라고 말하죠.

 

ag(n)<= f(n)<= bg(n)(참고: a와 b는 상수), Θ(g(n)) = f(n)

 

예를 들어 수행 시간이 T(n) = 3n^2 – 3n일 때 세타로 표현해 보아요.

 

T(n)은 n이 4보다 클 때 2n^2보다 크거나 같고 4n^2보다 작거나 같아요. 따라서 Θ(n^2)입니다.

 

1.3.2 O(빅 오)

O 표기는 점근적 상한을 표현하며 n이 특정 수보다 클 때의 점근적 최악을 말할 때 사용합니다.

 

f(n) <=ag(n) (a는 상수), O(g(n)) = f(n)

 

예를 들어 수행 시간이 T(n) = 3n^2 – 3n일 때 빅 오로 표현해 보아요.

T(n)은 n이 4보다 클 때 4n^2보다 작거나 같으므로 O(n^2)라고 말할 수 있습니다. 그리고 T(n) = 3n^2 – 3n은 n이 4보다 클 때 2n^3보다 작거나 같으므로 O(n^3)도 맞습니다. 여러분께서는 빅 오 표기로 나타낼 때 보다 정확하게 O(n^2)라고 표현하시는 것이 바람직하겠죠.

 

1.3.3 Ω(오메가)

Ω 표기는 접근적 하한을 표현하며 n이 특정 수보다 클 때의 점근적 최선입니다.

 

ag(n) <=f(n) (a는 상수), Ω(g(n))=f(n)

 

예를 들어 T(n) =3n^2-3n일 때 오메가로 표현해 보아요.

 

T(n)은 n이 0보다 클 때 3n^2보다 작거나 같으므로 Ω (n^2)입니다.

 

1.3.4 o(리틀 오)

o 표기는 접근적 상한보다 여유있는 상한입니다.

 

0<=f(n)<=ag(n),(a는 모든 양의 정수에 성립), o(g(n))=f(n)

 

예를 들어 T(n) = 2n일 때 리틀 오로 표현해 보아요.

 

만약 빅 오로 표현하면 O(n)도 맞는 표현이고 O(n^2)도 맞는 표현입니다. 하지만 리틀 오 표기에서는 모든 상수 a에 만족하지 못하기 때문에 o(n)은 틀린 표현입니다. o(n^2)라고 표현해야 합니다.

 

1.3.5 ω(리틀 오메가)

ω표기는 접근적 하한보다 여유있는 하한입니다.

 

0<= ag(n)<= f(n),(모든 양의 정수 a에 성립), o(g(n))=f(n)

 

예를 들어 T(n) = 2n^2일 때 리틀 오메가로 표현해 보아요.

오메가로 표현하면 Ω(n)과 Ω(n^2)은 모두 맞는 표현입니다. 하지만 리틀 오메가 표기에서는 모든 양의 정수 a에 ω(n^2)을 만족하지 못합니다. 따라서 ω(n)라고 표현해야 합니다.