[C언어] 점화식과 점근적 분석 방법(반복대치,추정후 증명, 마스터 정리)

쉽게 배우는 알고리즘 책을 참고했습니다.

 

안녕하세요!!

 

---

점화식

점화식이란? 어떤 함수를 자신과 똑같은 함수를 이용해서 나타내는 것입니다.

다시말해 재귀함수의 구조를 갖는 알고리즘만!! 점화식으로 표현할 수 있다 이말입니다.

재귀함수란?

F(n) = n * F(n - 1)  ; // 팩토리얼
F(n) = F(n - 1) + F(n - 2)  ;  // 피보나치 수
F(n) = F(n/2) + C  ; //데이터를 두가지로 나누는 정렬! 등..

 자기자신을 호출하는 형식을 갖는 것은 재귀함수라고 표현할 수 있습니다. 

 

F(n) = n^2 + n + 1 이런 형식은 쉽게 시간 복잡도를 구할 수 있지만,  자기 자신을 갖는 점화식일 경우에는 점화식의 점근적 분석 방법을 통해서 F(n) = F(n-1)+ ...의 형태를 F(n)  = n+ ...의 형태로 바꾸어야 시간 복잡도를 구할 수 있습니다.

 

예를 들어 

MergeSort(A[],p,r){
	if(p<r) then// 두개 이상의 수가 존재한다면  (상수 시간)
    {  
    	q<-[(p+r)/2]; //q = 반으로 나눈 값 (상수시간)
        MergeSort(A,p,q); // p~ r  까지의 구간중 반 구간인 p~ q까지 정렬 실행  T(n/2)
        MergeSort(A,q+1,r);  //q+1~ r 까지, 남은 배열의 구간을 정렬,   	T(n/2)
        Merge(A,p,q,r); //병합   (후처리 시간)
    }
}

위의 알고리즘을 보시면, MergeSort함수가 있습니다. 이 함수는 만약 배열A가 2개 이상의 구간이 존재한다면, 반으로 나눈 값을 q에 저장후 ( 배열 A 공간=> [p, , , , q,q+1, , , ,r]  ) q를 기준으로 p~q까지, 배열의 개수에 반을 sort할 수 있도록 MergeSort함수를 다시 호출하고, 연이어 나머지 반을 다시 MergeSort함수를 통해 호출을 합니다.

반으로 나누는 값, if(p<r)배열의 크기 판단값은 상수 시간에 해당됩니다.

※ 상수 시간은 점근적 수행 시간에 영향을 미치지 않으므로 제외해도 됩니다!!

따라서 점화식 T(n) 은 MergeSort(A,p,q) , MergeSort(A,q+1,r) => 배열의 크기에 반을 다시 MergeSort()함수로 호출하는 재귀구조형식을 두번 수행하므로 T(n) =2*T(n/2) + C(후처리시간+상수시간) 의 점화식을 갖게 됩니다.

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

점화식을 알고는 있지만 시간 복잡도의 표현 방법으로 표기를 바로 할 수 없기에 우리는 (1) 반복대치, (2) 추정후 증명, (3) 마스터정리 에 의해 점화식을 함수꼴로 변형해야만 시간 복잡도 표기 방법을 사용할 수 있습니다.

 (1) 반복 대치

 반복대치는 쉽게 말해서 T(n) = T(n-1)+C의 점화식이 있다면, (단 T(1) <=C)

T(n-1) 과, T(n-2), T(n-3)일때의 점화식을 T(n)점화식에 대입해서 (언제까지? T(1)이될 때 까지) 값을 알아가는 과정이라고 생각하시면 됩니다.

 

예를들어 T(n) = T(n -1)+C라는 점화식이 있다면 T(n-1) = T(n-2) +C 이고, T(n-2) = T(n-3) + C임을 구할 수 있습니다.

다시말해 T(n)의 점화식에, n의 자리에 n-1을 대입, n-2을 대입한 결과를 구할 수 있는 것입니다..

따라서    T(n) = T(n-1) + 1C   에 방금 구한 T(n-2)와 T(n-3)을 차례대로 대입하면

             T(n) = T(n-2) + 2C

             T(n) = T(n-3) + 3C    를 얻게됩니다.  특징이 보이시죠?

             T(n) = T(n-4) + 4C   이것을 n -1   -> 1 까지 반복하다보면!!

             T(n) = T(1)+(n-1)C 와 같아집니다. 이때 T(1) =<C이므로

             T(n) = C + nC - C   == nC 임을 얻을 수 있습니다.

             점화식 = 점화식의 꼴에서

             점화식 = n에 대한 다항식으로 바뀌었을 때 비로소 시간 복잡도의 표기 방법을 사용할 수 있습니다.

             따라서 T(n) =O(n)임을 구할 수 있습니다.

 

(2) 추정후 증명

 추정후 증명은 반복대치와는 반대로 먼저 점근적 복잡도를 가정한 다음에 그 가정이 맞는지! 귀납적으로 증명하는 방법입니다.

 예를들어 점화식 T(n) <= 2*T(n/2) + n의 식이 있을 때 우리는 쉽게 이 점화식이 분할정복에 의한 점화식임을 알 수 있습니다. (사실 저도 어렵긴한데,, 저위의 식은 몇번 알고리즘을 파악하다보면 금방 Sorting에 관한 식임을 알 수,,있을것닙니다) 분할정복의 시간 복잡도는 식에 따라서 O(n*logn) 이거나 O(logn)입니다.

하지만 위의  식에서 시간 복잡도는 O(nlogn)이므로

우리는 빅오 표기법의 정의 인 f(n)<=c*g(n)  ,,점근적 상한의 정리를 이용해

T(n)<=c*n*log n을 만족하는 양의 상수 C를 구하게 된다면

이 추정은 증명이 되는 것입니다..

따라서 T(n) = c*n*log n 의 식을 이용해 T(n/2), n/2를 대입하면 T(n/2) =<c*(n/2)*log(n/2)를 구할 수 있고 방금 구한식을 T(n)<=2*T(n/2) + n 여기 형광등 색에 대입한 식 <= C*nlogn을 만족하는 상수 C하나만 구하게 된다면 증명은 성공하는 방법입니다.

 

(3) 마스터 정리

 제가 봤을 땐 반복대치랑 마스터정리가 가장 쉬운 것 같습니다. 특히 마스터 정리는 공식만 알 고 있다면 쉽게 점화식의 복잡도를 구할 수 있기 때문이죠,,

여기서 밑줄친 부분이 가장 중요합니다. 왜냐면 f(n)/h(n)이 리미트 극한으로 갔을 경우 수렴하는지, 발산하는지 ,0으로 수렴하는지 에 따라서 시간 복잡도 표현의 결과가 달라지기 때문입니다. 

lim         f(n)/h(n)의 식에서

n->무한대

 

h(n)이 클 경우 0으로 수렴하고 이때의 T(n) = 빅세타(h(n))이 되고,

f(n)이 클 경우 무한대로 발산하고, 이때의 T(n) = 빅세타(f(n)) 이 됩니다.

만약 f(n)/h(n)이 n / n과 같을 경우 1,2등 상수로 수렴할 경우 T(n) =   빅세타(h(n)logn)의 결과를 얻습니다.

 

다음 글은 점화식을 점근적 분석으로 문제 해결하는 과정으로 찾아오겠습니다!!