저자 Dasgupta의 Algorithms을 해석하면서 정리한 글입니다.

2.2 Recurrence relations

점화식(Recurrence): 어떤 함수를 자신과 똑같은 함수를 이용해 표현한 식
ex) 피보나치 수열 : $F(n) = F(n-1) + F(n-2)$

알고리즘의 시간 복잡도를 계산하다보면 아래와 같은 점화식이 생성된다.
이는 Master theorem의 점화식으로 특정 형태의 재귀식에서 바로 결과를 도출하는 방법이다.

• 입력의 크기가 n인 문제를 풀기 위해 입력의 크기가 ${b \over n}$인 문제를 풀고, 나머지 $f(n)$의 오버헤드가 필요한 알고리즘의 점화식을 풀 수 있습니다.

$T(n) = aT({n\over b}) + O(n^d)$

여기서 $a > 0, b > 1,$ and $d \geq 0$를 만족할 경우

$T(n)$ =

(1) $O(n^d)$ if $d > log_ba$
(2) $O(n^dlogn)$ if $d = log_ba$
(3) $O(n^{log_ba})$ if $d < log_ba$

위와 같이 시간복잡도가 계산됩니다.

ex 1) 　　 $T(n) = 9T(n / 3) + n$
$a = 3, b = 3, f(n) = n$
$n<n^{log_39}=n^2$ 이므로 3번 경우에 해당합니다. 그러므로 시간 복잡도는 $T(n) = \Theta(n^2)$ 입니다.

ex 2) 　　 $T(n) = T(2n / 3) + 1$
$a = 1, b = 3/2, f(n) = 1$
$n^{log_{3 \over 2}1}=n^0=1$ 이므로 1번 경우에 해당합니다. 그러므로 시간 복잡도는 $T(n) = \Theta(logn)$ 입니다.

여기서 a는 재귀 함수에서 불러오는 재귀함수의 개수, b는 한 재귀함수 내에서 제공되는 배열에서 사용하는 부분, d는 반복문의 복잡도로 나타낼 수 있습니다.

예를 들어 이진탐색을 구현한 코드를 살펴보겠습니다.

int BinarySearch(std::vector<int>& A, int low, int high, int target) {
	if (low >= A.size() || high >= A.size()) {
		return NOT_FOUND;
	}
	if (high < low) {
		return NOT_FOUND;
	}
	int mid = low + (high - low) / 2;
	if (target == A[mid]) {
		return mid;
	} else if (target < A[mid]) {
		return BinarySearch(A, low, mid - 1, target);
	} else {
		return BinarySearch(A, mid + 1, high, target);
	}
}

위 코드를 살펴보면, n만큼의 공간이 있는 배열 A에서 반절을 나눠 n/2만큼의 공간을 탐색하는 것이므로 b는 2가 됩니다.
프로그램의 흐름이 BinarySearch(A, low, mid - 1, target)로 갈것이나 BinarySearch(A, mid + 1, high, target)로 가던지 한방향으로 갈 수 있으므로 a는 1이 됩니다.
반복문이 없으므로 $n^0 = 1$ , 결국 $d=0$이 됩니다.

$d$가 $log_ba$ 보다 작으므로 $n^{log_ba} = 1^{log_2n} = O(logn)$이 됩니다.

마스터 정리를 쓰기 위해선 세 가지 제약조건이 있습니다.

1. $f(n)$은 다항식(polynomial function)이어야 합니다. 단 $f(n)$이 다항식이 아니더라도 극명하게 적용될 수 있음을 증명하면 사용할 수 있습니다. ($n^2 > nlogn$ 또는 $n^2 < n^2logn$)

2. $a \geq 1$와 $b >1$인 양의 실수이어야 합니다. 재귀를 호출할 때 그 호출 비용이 현재보다 작아야 한다는 것을 의미합니다. b가 1보다 작거나 같으면 오히려 문제가 그대로거나 커진다는 것을 의미합니다.

3. 정규 조건(Regularity condition)인 $af(n/b) \leq cf(n)$과 $c<1$을 만족하는 $c$가 존재해야 합니다. 이것 역시 subproblem이 현재 problem보다 작아져야 함을 의미합니다. 만약 $f(n)$이 지수 함수, 주기 함수의 경우 의심해봐야 합니다.

확장 마스터 정리(Extended or Advanced master theorem)

$f(n) =nlogn$인 경우 다항식이 아니기 때문에 마스터 정리를 이용할 수 없습니다. 하지만 확장 마스터 정리를 사용하면 시간 복잡도를 구할 수 있습니다. 이를 적용하기 위해 $f(n)$을 일반화 시켜줍니다.

여기서 $a$와 $b^k$를 비교하여 여러 케이스로 나뉩니다.

Reference

1. Algorithms - Dasgupta
2. https://en.wikipedia.org/wiki/Master_theorem_(analysis_of_algorithms)
3. https://dad-rock.tistory.com/19
4. https://ferrante.tistory.com/47
5. https://coloredrabbit.tistory.com/94
6. https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=qkrgustnrk&logNo=220765180470