점화식과 알고리즘 복잡도 분석

1. 점화식의 점근적 분석 방법

1) 반복대치

우선 병합정렬의 알고리즘은 아래와 같다.

Merge sort의 전체 걸리는 시간을 T(n)이라고 하면 3,4번째줄은 각각 절반을 merge sort하는 것임으로 T(n/2)가 걸리게 된다. 그리고 5번째 줄은 3,4에서 구한 값을 합치는 것인데 이를 정렬이 될때까지 반복하면 최대 5번째 줄을 n-1번 반복하게 된다.(n개가 역순으로 되어있을때) 즉 걸리는 시간을 다 합치면 을 얻을 수 있다.여기서 점근적 복잡도의 계산을 용이하기 하게 위해 주로 라고 둔다.

은 항상 만족하고 이므로 이여서 알고리즘 분석에 영향을 주지 않는다.

이를 이용하여 위의 Mergesort를 분석해보자.

임고 여기서 라고 해보자. 그러면가되면서 마지막줄이 가된다. 따라서

를 얻을 수 있다. 

 

2) 추정 후 증명

식의 모양을 보고 점근적 복잡도를 추정한 후 그것의 옳음을 귀납적으로 증명하는 방법이다. 아래의 예시를 보자. 

의 점근적 복잡도는 T(n)=O(nlogn)이다. 이를 위해서는 우선 인 양의 상수 c가 존재하면 된다. 따라서 아래처럼 증명이 가능하다.

 

3)마스터 정리 

특정 모양의 재귀식에서 바로 결과를 알 수 있다. 그 식의 모양은 아래와 같다.

위의 의미는 입력의 크기가 b인 문제를 풀기 위해 입력의 크기가 n/b인 문제 a개를 풀고 나머지 f(n)만큼의 시간이 걸린다는 것이다. 위의 병합정렬도 a=b=2이고 f(n)=n이므로 이에 해당한다. 위의 결과는 f(n)의 모양에 다라 정해지는데 이라할때 3가지로 나누어진다.

1. 어떤 양의 상수 ε에 대해서 이면 T(n) = Θ(h(n))이다.

2. 어떤 양의 상수 ε에 대해서 이고, 어떤 상수 c와 충분히 큰 모든 n에 대하여 이면 T(n) = Θ(f(n))이다.

3.이면 T(n) = Θ(h(n)logn)이다.

이를 근사버전으로 만든 것은 아래와 같다.

이를 이용해서 예를 들어보면 에서 이다. 이므로 이다.

 

쉽게 배우는 알고리즘을 공부하면서 정리한 내용입니다.