알고리즘...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로 가정해도 문제가 없게 된다.