02. 알고리즘 분석

알고리즘의 효율성 분석을 위한 만능 공식은 없음. 대신, 몇몇 기본적인 방법들이 존재함.

알고리즘 분석은 대체로 안에서 바깥쪽으로 진행됨.

 

1. 순차적 규칙(Sequencing Rule)

위와 같은 알고리즘을 가정함

P1과 P2가 알고리즘의 두 부분이라고 한다면,

각각은 하나의 명령어이거나 복잡한 서브-알고리즘일 것임.

추가로, t1과 t2를 P1과 P2의 실행에 걸리는 시간이라고 했을 때

순차적 규칙에 의하면, P1과 P2의 실행에 거리는 시간은 단순히 t1+t2임.

최대 규칙(Maximum Rule)에 따르면, 이 시간은 θ( max{t1, t2} )임.

 

2. for 반복문

for i ← 1 to m, do
	P(i);

이 반복은 큰 알고리즘의 일부이고, 사이즈 n짜리 인스턴스에서 동작함.

 

2-1. P(i)에 걸리는 시간이 i와 관계가 없을 때 (= 모든 P(i)에 걸리는 시간이 동일할때)

P(i) 실행에 걸리는 시간이 t라 가정하면,

P(i) 의 실행은 m 번 반복 되고, 각각 t 시간만큼 걸리므로, 해당 반복문은 총 mt 만큼 걸림.

 

2-2. P(i)에 걸리는 시간이 i와 관계가 있을 때

P(i)에 걸리는 시간 관련 함수를 t(i)라 가정. t(i)는 i 뿐 아니라 인스턴스 크기 n이나, 인스턴스 자체에도 영향을 받을 수 있음. 반복에 걸리는 총 시간은 $\sum_{i=1}^m t(i)$임.

 

3. 재귀 호출

알고리즘을 간단히 살펴보다보면 종종 회귀적인 방정식으로 표현 가능한걸 알 수 있음.

일단 회귀적인 방정식이 얻어지면, 일반적인 방법을 사용해 간단한 비재귀적인 점근 표기법으로 변환이 가능함.

 

예시 < 피보나치 수열 >

$f_0 = 0, f_1 = 1 (n<2 $ 인 경우$)$

$f_n = f_{n - 1}+f_{n - 2} (n\geq2$ 인 경우$)$

function Fibrec(n)
	if ( n < 2 )
	then return n
	else return ( Fibrec(n-1) + Fibrec(n-2) )

T(n) 이 Fibrec(n)에 걸리는 시간이라 가정.

n < 2 인 경우, T(n)은 상수 시간 a 만큼 걸림. (Big-O로는 O(1)로 표기)

그 외의 대부분의 작업은 두 재귀 호출에서 이루어지며, 이는 각각 T(n-1), T(n-2) 만큼 걸림.

추가로, $f_{n-1}$과 $f_{n-2}$의 합하는 시간이 필요함 ( T(n-1)+T(n-2) )

h(n) 이 그 합하는 시간과 재귀 제어에 필요한 시간이라고 가정하면, T(n)은 다음과 같음.

 

※참고※ 탐색 알고리즘 종류와 시간 복잡도

a. 정렬 + 이분 탐색 < O(nlogn) + O(logn) >

b. 선형 탐색 < O(n) >

c. 해싱 < O(1) >

 

4. while 과 repeat(= do-while) 반복문

몇 회 반복할지 명시되어 있지 않아서 for문에 비해 예측이 어려움.

가장 쉬운 방법은 매번 반복될 때마다 줄어드는 변수와 관련된 함수를 찾는 것임.

재귀 알고리즘처럼 접근하는 방법도 있음.

 

예시 < 이분 탐색 >

감소하지 않는 순서(크거나 같은 순서)로 정렬된 배열 D[1, ..., n] 안에서 요소 x의 인덱스 i 찾기.

h 는 head, t 는 tail 의 약자

function BinartSearch (D[1, ..., n], x)
{
	h ← 1; t ← n;
	while ( h < t ) do
	{
		m ← ( h + t ) / 2			# d
        	case x < D[m] : t ← m-1;		# case 1
        	case x = D[m] : h, t ← m; return m;	# case 2
        	case x > D[m] : h ← m+1;		# case 3
 	}						# d^ (d caret)
	return (h);	#not found
}

 

4-1. 표준적인 방법

d = t - h + 1 (d는 배열 D의 총 요소 개수)

처음에, d = n임.

반복은 $h\geq t$이면 끝나며, 이는 의미상으로 $d\leq 1$와 같음.

$d$ 와 $\hat{d}$가 각각 반복 전과 후의 $t - h + 1$값이라고 가정.

 

case 1 )  (상단 코드 주석에 달린 case 참고)

case 3 )

case 2 )

어떠한 경우에도 $\hat{d} = d/2$ 라는 결론이 나오며, 이는 매 반복마다 d가 최소 절반으로 줄어든다는 것을 의미함.

 

- 이분 탐색의 최대 실행 시간

$d_l$이 $l$번째 반복($l\geq 1$) 이후 $t-h+1$값을 의미하고, $d_0=n$이라 가정하면,

$d_{l-1}$은 $l$번째 반복 전의 $t-h+1$값이므로, 모든 $l\geq 1$에 대해 $d_l\leq d_{l-1}\div 2$임이 증명됨.

수학적 귀납법에 의해, $d_l\leq n\div 2^l$임.

반복은 $d\leq 1$일때 끝나고, 이는 $l=$⌈ $log_2 n$ ⌉일때 임. (⌈ ⌉ 기호는 올림을 의미함.)

결론적으로, 반복은 최대 ⌈ $log_2 n$ ⌉ 번 만큼 실행되고 각 반복은 상수 시간($O(1)$)만큼 걸리므로, 이분 탐색은 $O(log_2 n)$의 시간복잡도를 가짐.

 

4-2. while 반복문을 재귀처럼 생각하기

매 반복마다, 배열 내 x의 범위를 줄여 나감.

t(d)가 $t-h+1\leq d$일때 while 반복문을 끝내기 위한 최대 시간이라 가정. (=고려해야할 요소의 수가 최대 d 개 있음.)

매 반복마다, t - h + 1은 최소 절반으로 줄어듬.

재귀적으로, 이는 t(d)가 매 반복 마다 최대 $b+t(d\div 2)$ 만큼의 시간을 필요로 한다는 것을 의미함.

b와 c는 상수

function BinarySearch ( D[1, n], x )
{
	k ← ( 1+n ) ÷ 2
	if ( D[k] = x ) then return k;
	if ( x < D[k] ) then return ( BinarySearch( D[1, k-1], x) );
	if ( x > D[k] ) then return ( BinarySearch( D[k+1, n], x) );
}

t(n) 이 BinarySearch( D[1,n], x )를 호출해서 사용되는 시간이라고 할 때, 증명은 다음과 같음.

※ 마스터 정리(Master Theorem)

상수 $n_0\geq 1,  l\geq 1,  b\geq 0,  k\geq 0$는 정수이고, $c$는 0이 아닌 양의 실수 임.

$ T:N→R^+ $ 가 감소하지 않는(non-decreasing) 함수라 가정할때 $T(n) = l*T(n/b)+c*n^k (n\geq n_0)$ 라면, 시간 복잡도는 다음과 같음.