알고리즘...6

점화식의 점근적 분석 방법

대표적인 방법으로 반복 대치, 추정후 증명, 마스터 정리가 존재한다.

 

- 반복 대치

: 어떤 함수의 입력이 n일 때 소요 시간을 T(n)이라 할 경우 T(n)을 T(n - 1)로 대치하고 T(n - 1)을 T(n - 2)로 대치하는 것을 반복하여 T(1)까지 대치하는 분석 방법이다.

 

---

어떤 함수의 입력이 n일 때 소요 시간 T(n)은 다음과 같이 나타낼 수 있다.

 

T(n) = T(n - 1) + c

 

이때 c는 자기 호출을 제외한 나머지를 수행하는 시간을 나타낸다. 

---

 

병합 정렬 알고리즘의 반복 대치를 통한 분석은 다음과 같이 진행할 수 있다.

 

MergeSort

MergeSort(A[], p, r)
{
	if (p < r) then {
    	q ← |_ q + r / 2 _|
        MergeSort(A[], p, q)
        MergeSort(A[], q + 1, r)
        Merge(A, p, q, r)
    }
}

 

입력이 n 일 때 소요 시간을 T(n)이라고 하면 다음과 같이 나타낼 수 있다.

 

A: 병합 정렬을 반으로 나눠 실행하기 때문에 발생

B: 병합 정렬 후 통합 작업 실행으로 발생

 

이를 전개하면 다음과 같다.

 

※ n = 2^k로 가정해도 일반성을 잃지 않으므로 이를 k에 대한 식으로 쓰면 k = logn이 된다.

 

---

n = 2^k로 가정해도 되는 이유는 다음과 같다.

 

어떤 n이라도 n과 2n 사이에는 2의 멱수가 하나 존재한다.

이때 임의의 상수 r에 대해 T(n) = O(n^r)이면 T(2n) = O((2n)^r) = O(2^rn^r) = O(n^r)이므로 T(2n) = T(n)이 된다.

 

이를 위의 사실에 대해 적용하면

T(n) ≤ T(2^k) ≤ T(2n)으로 볼 수 있고 이때 T(n) = T(2n)이므로 T(n) = T(2^k) = T(2n)의 관계가 성립한다.

 

그러므로 n 이후로 처음 만나는 2의 멱수도 항상 n에 대한 함수와 같은 점근적 복잡도를 지니므로 n = 2^k로 가정해도 문제가 없게 된다.

---

 

참고문헌

한빛아카데미.문병로.(2016.07.24).쉽게 배우는 알고리즘