[84] 알고리즘 03차시 점화식과 점화식의 점근적 분석

1. 알고리즘과 문제 해결

가. 문제해결 전략

주어진 조건에 맞추어 다각도로 문제에 접근

문제를 철저히 분석

그림을 그리거나, 식을 만들거나, 또는 규칙 찾기

조건에 따라 거꾸로 생각해보기

단계적으로 생각하기(알고리즘)

2. 점화식

가. 점화식(Recurrence Relation)

어떤 함수를 자신보다 더 작은 변수에 대한 함수와의 관계로 표현한 것

자기호출을 사용하는 함수(재귀)의 복잡도를 구하는데 유용함.

수열은 원소들을 일정한 순서로 나열한 형태로 표현하는데 이러한 원소들 사이에는 일정한 규칙이 있을 수 있고 원소들의 나열 대신 이 규칙으로 표현하는 것도 점화식임

https://ko.wikipedia.org/wiki/점화식

점화식 - 위키백과, 우리 모두의 백과사전

나. 병합 정렬을 이용한 점화식의 수행 시간

병합 정렬도 자신보다 더 작은 변수에 대한 함수와의 관계로 표현 가능

입력의 크기가 n인 배열을 병합 정렬하려면 일단 배열을 이등분한 다음 각각을 재귀적으로 병합해 이들을 다시 병합함으로써 정렬이 끝남.

https://ko.wikipedia.org/wiki/합병_정렬

합병 정렬 - 위키백과, 우리 모두의 백과사전

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

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

1) 반복 대치

더 작은 문제에 대한 함수로 반복해서 대치해 나가는 해법

2) 추정 후 증명

결론을 추정하고 수학적 귀납법을 이용하여 증명하는 방법

3) 마스터 정리

형식에 맞는 점화식의 복잡도는 복잡한 계산이나 증명 없이 바로 알 수 있음.

\(a \geq 1\), \(b \geq 1\)에 대해 \( T(n) = aT(n/b) + f(n) \)인 점화식에서 \( n^{\log{ba}} = h(n) \)이라 할 때, \(h(n)\)과 \(f(n)\)의 상대적 무게에 따라 전체 복잡도가 결정됨.

마스터정리
1. 어떤 양의 상수 \(\epsilon\)에 대하여 \(f(n)/h(n) = O(1/n^{\epsilon})\)이면, \(T(n) = \Theta(h(n))\)이다.
2. 어떤 양의 상수 \(\epsilon\)에 대하여 \(f(n)/h(n) = \Omega(1/n^{\epsilon})\)이고, 어떤 상수 \(c < 1\)와 충분히 큰 모든 \(n\)에 대해 \(af(n/b) \leq cf(n)\)이면 \(T(n) = \Theta(f(n))\)이다.
3. \(f(n)/h(n) = \Theta(1)\)이면 \(T(n) = \Theta(h(n)\log{n})\)이다.

마스터정리 근사버전
1. \(\displaystyle \lim_{n \to \infty } \frac {f(n)} {h(n)} = 0\)이면, \(T(n) = \Theta(h(n))\)이다.
2. \(\displaystyle \lim_{n \to \infty } \frac {f(n)} {h(n)} = \infty\)이고, 충분히 큰 \(n\)에 대해 \(af(n/b) \leq cf(n)\)이면 \(T(n) = \Theta(f(n))\)이다.
3. \(\displaystyle \frac {f(n)} {h(n)} = \Theta(1)\)이면 \(T(n) = \Theta(h(n)\log{n})\)이다.

마스터정리 대략정리
1. \(h(n)\)이 더 무거우면 \(h(n)\)이 수행 시간을 결정한다.
2. \(f(n)\)이 더 무거우면 \(f(n)\)이 수행 시간을 결정한다.
3. \(h(n)\)과 \(f(n)\)이 같은 무게이면 \(h(n)\)에 \(\log{n}\)을 곱한 것이 수행 시간이 된다.

https://ko.wikipedia.org/wiki/마스터_정리

마스터 정리 - 위키백과, 우리 모두의 백과사전