[알고리즘 C언어] 1. 2 알고리즘의 평가와 접근적 표기

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

 

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

 

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

 

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

 

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

 

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

 

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

 

1.2.1  Θ(세타, Theta)

Θ 표기는 점근적으로 평균을 표현하는 표기입니다. 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.2.2 O(빅 오,Big 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.2.3 Ω(오메가, omega)

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

 

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

 

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

 

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

 

1.2.4 o(리틀 오, little 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.2.5 ω(리틀 오메가, little omega)

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

 

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

 

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

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


학습에 도움이 되시면 ebook을 구입(판매가 3000원, ebook)하여 소장하시면 감사하겠습니다.

언제나 휴일 출판사의 수익금의 대부분은 아프리카에 기부하고 있습니다.

디딤돌 알고리즘 C언어는 디딤돌 자료구조와 알고리즘 with C언어에서 알고리즘 부분을 다루고 있어서 많은 부분에서 비슷합니다.