[알고리즘] 분석

1) 정확성 분석

유효한 입력에 대해 유한시간 내에 정확한 결과를 만들어 내는지 확인하는 것입니다.

이러한 확인은 수학적 기법을 사용하여 이론적으로 증명합니다.

 

2) 효율성 분석

효율성 분석은 알고리즘 수행에 필요한 컴퓨터 자원의 양을 측정, 평가하는 것입니다.

이러한 효율성 분석에는 공간복잡도, 시간복잡도가 있습니다.

 

1. 공간복잡도

컴파일하는 시점에서 발생하는 메모리와 알고리즘을 수행할때 필요한 메모리가 있는데 이러한 총 메모리양이 필요한지 측정하는 것입니다.

 

2. 시간복잡도

시간 복잡도는 알고리즘의 실행부터 완료까지 걸리는 시간을 분석하는 것입니다.

 

알고리즘의 수행시간은 각 연산이 수행되는 횟수의 합이라고 볼 수 있습니다

이러한 수행시간에 영향을 미치는 요인에는 여러가지가 있습니다.

 

첫번째로 입력크기 입니다.

예컨대, 리스트 원소의 개수나 행렬의 크기 등이 크다면 수행시간이 길어질 것입니다.

이러한 입력크기 n의 함수 f(n)으로 수행시간을 계산합니다.

 

두번째로 입력데이터의 상태입니다.

입력데이터의 상태로 알고리즘의 수행시간을 계산하는 것은 3가지 방법이 있습니다.

 

첫번째 방법은 평균수행시간을 사용하는 것입니다. 이 방법은 모든 상태를 고려하여 해당 수행시간의 평균으로 총 수행시간을 계산합니다. 이론적으로 가장 좋은 방법이긴 하나 모든 경우의 수를 알 수 없고 모든 수행시간을 계산할 수 없기 때문에 현실적으로 사용하기 불가능합니다.

 

두번째는 최선의 수행시간입니다. 경우의 수를 모두 알 수없고 모든 수행시간을 알 수는 없지만, 알 수 있는 가장 작은 수행시간을 수행시간으로 계산하는 것입니다.

 

세번째로는 최악의 수행시간입니다. 최선의 수행시간과는 반대로 가장 오래걸리는 시간을 수행시간으로 계산하는 것입니다. 

 

일반적으로 입력데이터의 상태로 수행시간을 계산할때는 최악의 수행시간을 사용합니다. 왜냐하면 알고리즘을 분석할때는 상대적으로 계산하기 때문에 최악의 수행시간으로 비교하는 것이 더 정확하다고 볼 수 있습니다.

예컨대 A,B 두개의 알고리즘을 비교할때 A는 최선의 수행시간이 1초 최악의 수행시간이 100초라고 하고 B는 최선의 수행시간이 3초 최악의 수행시간이 10초라고 한다면 총 수행 개수를 알수는 없겠지만, 나머지의 수행개수들의 수행시간은 최선과 최악의 사이라고 할 수 있으므로 B가 더 효율적이라고 볼 수 있습니다.

 

 

상대적으로 공간복잡도는 계산하기 쉽고 크게 문제가 발생하지 않기 때문에 일반적으로 효율성을 분석한다고 하는 것은 시간복잡도를 개선하는 것을 의미합니다.

 

3. 점근성능

점근성능이란 입력크기 n이 무한히 커짐에 따라 결정되는 성능을 의미합니다.

이러한 점근성능의 결정방법은 먼저 입력크기가 충분히 커짐에 따라 함수값에 가장 큰 영향을 미치는 차수를 찾습니다. 그 다음에는 수행시간의 다항식 함수에서 최고차항만을 계수없이 취해서 표현합니다.

따라서 점근성능은 정확한 값이 아닌 어림값으로 계산합니다. 

 

예컨대 f1(n) = 5n+200 과 f2(n) = 2n^2+3n+10의 두개의 함수가 있다고 합니다.

n=1 일때는 f1(1) = 5*1+200 = 205,  f2(1) = (2*1)^2 + 3*1+10 = 17입니다. 따라서 f2(n)의 성능이 더 좋다고 할 수 있습니다.

그러나 n이 충분히 커져서 n=10이 된다면 f1(10) = 5*10+200=250, f2(10) = (2*10)^2+3*10+10 = 440이 되어 f1(n)의 성능이 더 좋아집니다. 이럴때 f2(n)에서 가장 큰 영향을 미치는 것은 n^2입니다.

 

따라서 점근성능은 f1(n) = n, f2(n) =n^2으로 f1(n)의 성능이 더 좋다고 할 수 있습니다.

 

이러한 점근성능을 표현하는 방법으로는 big-oh, big-omega, big-theta 표기법이 있습니다.

 

1. big-oh(점근적 상한)

수학적 정의는 다음과 같습니다.

함수 f와 g를 각각 양의 정수를 갖는 함수라고 가정했을 때 
어떤 양의 상수 c와 n0이 존재하여 모든 n >= n0에 대하여
f(n) <= c*g(n)이면 f(n) = O(g(n))이다.

 

결과적으로 본다면 최악의 수행시간을 의미합니다.

big-oh에 따른 연산시간의 증가 추세는 아래와 같습니다.

2. big-omega(점근적 하한)

수학적 정의는 다음과 같습니다.

함수 f와 g를 각각 양의 정수를 갖는 함수라고 가정했을 때 
어떤 양의 상수 c와 n0이 존재하여 모든 n >= n0에 대하여
f(n) >= c*g(n)이면 f(n) = Ω(g(n))이다.

 

결과적으로 본다면 최선의 수행시간을 의미합니다.

3.big- theta(점근적 상하한)

수학적 정의는 다음과 같습니다.

함수 f와 g를 각각 양의 정수를 갖는 함수라고 가정했을 때 
어떤 양의 상수 c1,c2와 n0이 존재하여 모든 n >= n0에 대하여
c1*g(n) <= f(n) <= c2*g(n)이면 f(n) = Θ(g(n))이다.

 

위의 정의에서 c1*g(n) = Ω가 되며 c2*g(n)은 O가 됩니다. 

 

주요 O-표기간 연산시간의 크기 관계는 다음과 같습니다.

4. 알고리즘의 시간 복잡도 구하기

이론적으로 알고리즘의 시간복잡도를 구하기 위해서는 기본연산의 수행횟수의 합인 f(n)을 구한 후, f(n) = O(g(n))을 만족하는 최소차수의 함수 g(n)을 찾습니다.

 

그러나 실용적인 방법으로는 알고리즘의 모든 문장이 아닌 루프의 반복횟수만을 조사하여 최고차수를 시간 복잡도로 하면됩니다.

 

예제1) 주석은 수행횟수입니다.

i = 1; //1
while(i <= n){ //n+1
 x = x+1; //n
 i = i+1; //n
}

 

위의 반복문을 함수로 구하면 f(n) = 3n+2가 됩니다. 

따라서 시간 복잡도는 O(n)이 됩니다. 

 

예제2)

count = 0; //1
for(i=0;i<n;i++) //n+1
	for(j=0;j<n;j++) // n+1
    	count ++; //n^2
print count; //1

위의 반복문을 함수로 구하면 f(n) = n^2+2n+4

따라서 시간 복잡도는 O(n^2)이 됩니다.

 

5. 순환(재귀) 알고리즘

 순환 알고리즘은 알고리즘의 수행과정에서 자기자신의 알고리즘을 다시 수행하는 형태를 의미합니다.

분할정복 방법이 적용된 알고리즘은 기본적으로 순환 알고리즘 형태를 가집니다.

 

아래코드는 예제입니다(이진탐색)

BinarySearch(A[],key,left,right){
	if(left > right) return (-1);
    mid = |(left+right)| / 2;
    if(A[mid] == key) return (mid);
    else if(key < A[mid])BinarySearch(A,key,left,mid-1)
    	else BinarySearch(A,key,mid+1,right);
}

 

조건에 따라 BinarySearch 함수가 다시 수행되는 것을 확인할 수 있습니다.

 

6. 점화식과 폐쇄형

순환 알고리즘은 수행횟수를 정확하게 알 수 없기 때문에 일반적으로 점화식으로 표현합니다.

점화식에서 T는 수행시간을 의미합니다.

 

점화식의 폐쇄형을 구하는 방법은 아래와 같습니다.

 

그런데 점화식을 매번 구할수는 없기 때문에 암기하는 것이 좋습니다.

 

따라서 기본점화식은 외우는 것이 좋습니다.

기본점화식					폐쇄형
(1)	T(n) =	Θ(1)	n=1	→	T(n) = Θ(n)
		T(n-1)+Θ(1)	n>=2
(2)	T(n) =	Θ(1)	n=1	→	T(n) = Θ(n2)	퀵정렬에서 사용(최악)
		T(n-1)+Θ(n)	n>=2
(3)	T(n) =	Θ(1)	n=1	→	T(n) = Θ(logn)	이진탐색
		T(n/2)+Θ(1)	n>=2
(4)	T(n) =	Θ(1)	n=1	→	T(n) = Θ(n)
		T(n/2)+Θ(n)	n>=2
(5)	T(n) =	Θ(1)	n=1	→	T(n) = Θ(n)
		2T(n/2)+Θ(1)	n>=2
(6)	T(n) =	Θ(1)	n=1	→	T(n) = Θ(nlogn)	합병정렬
		2T(n/2)+Θ(n)	n>=2			퀵정렬(최선)

 

입력의 크기에 따라 수행시간의 차이가 극명하게 날 수 있으므로 효율적인 알고리즘을 설계하고 선택하는 것이 중요합니다.