점화식

점화식이란

점화식이란 쉽게 말해, 어떤 함수를 자기 자신과 똑같은 함수를 이용하여 나타내는 것입니다. 동일한 함수가 등호 혹은 부등호의 양쪽에 나타나는데, 이 때 양쪽 함수의 변수 크기는 다릅니다.

예를 들어, n!의 점화식은 f(n) = nf(n - 1)으로, 피보나치 수열의 점화식은 f(n) = f(n - 1) + f(n - 2)로 나타낼 수 있습니다.

점화식은 재귀 함수의 복잡도를 구하는데 유용한데, 병합 정렬의 핵심부를 예로 살펴봅사다:

mergeSort(A[], p, r) { // A[p...r]을 정렬
  (1.) if (p < r) then {
    (2.) q ← ⌊(p + r) / 2⌋ // p, r의 중간 지점 계산
    (3.) mergeSort(A, p, q) // 전반부 정렬
    (4.) mergeSort(A, q + 1, r) // 후반부 정렬
    (5.) merge(A, p, q, r) // 병합
  }
}

mergeSort 알고리즘은 (②) 주어진 문제를 이등분한 다음, (③, ④) 나누어진 두 문제를 각각 해결하고, (⑤) 후처리를 함으로써 끝납니다.

크기가 n인 배열을 정렬하는 문제에 크기가 n/2인 배열을 정렬하는 문제 두 개가 포함됩니다. 따라서 입력의 크기가 n인 병합 정렬의 수행 시간이 T(n)이라고 하면, 다음과 같이 표현할 수 있습니다:

$T(n) = 2T(\frac{n}{2}) + 후처리 시간 (여기서는 n)$

이 때 ①과 ②는 점근적 수행 시간에 큰 영향을 미치지 않으므로 제외하고 생각해보면, T(n)은 크기가 절반인 두 개의 문제를 해결하는 시간과 이들을 병합하는 (후처리)시간으로 구성됩니다.

이때 함수 T(n)은 자신보다 크기가 절반인 변수로 표현된 함수를 포함하는 “점화식”입니다.

만약 입력의 크기가 n인 문제를 해결하는 어떤 알고리즘이 자신보다 크기가 $\frac{1}{3}$인 문제를 네 번 푼다면, 수행 시간은 다음과 같은 점화식으로 나타낼 수 있습니다:

$T(n) = 4T(\frac{n}{3})$

점화식의 점근적 분석방법

점화식으로 표현된 식의 점근적 복잡도를 구하는 방법에는 크게 세 가지가 존재합니다:

반복 대치

n!을 구하는데 소요되는 시간을 T(n)이라 한다면, T(n)을 다음과 같이 나타낼 수 있습니다:

T(n) = T(n - 1) + c (이 때 c는 재귀호출을 제외한 나머지 수행 시간. 곱셈, return 등.)

즉, n의 팩토리얼을 구하는 시간은 n - 1의 팩토리얼을 구하는 시간에 상수 시간을 더하는 것과 같습니다.

n의 크기가 1이면 T(1) ≤ c 이므로 T(n)을 다음과 같이 전개할 수 있습니다:

  T(n) = T(n - 1) + c
= T(n - 2) + c + c = T(n - 2) + 2c
= T(n - 3) + c + 2c = T(n - 3) + 3c
...
= T(1) + (n - 1)c
≤ c + (n - 1)c
= cn

따라서 T(n) ≤ cn 이므로 T(n) = O(n) 입니다.

종합하자면, 반복대치란 위와같이 T(n) 을 T(n - 1)로 “대치”하고, T(n - 1)을 T(n - 2)로 “대치하고” ⋯ 최종적으로 T(1)까지 “반복해서 대치”해서 점근적 복잡도를 구하는 방법을 말합니다.

점근 복잡도의 계산을 편하게 하기 위해 흔히 $n = 2^k$라고 가정합니다 (이 때 k는 양의 정수). 그 이유를 설명하자면, 어떤 정수 $n$이든 간에, $n$과 $2n$ 사이에는 2의 멱수가 존재합니다. 즉 $n ≤ 2^k < 2n$인 $2^k$가 존재한다는 뜻입니다.

즉, $n ≤ 2^k < 2n$ 라면 $n=2^k$로 놓고 복잡도를 구하겠다는 것입니다. $n$과 $2n$은 크기가 두 배 차이나는데, 두 배 차이가 나는 입력에 대해서는 다항 시간이 걸리는 모든 알고리즘은 같은 복잡도를 가집니다. 왜냐하면 임의의 상수 $p$에 대해, $T(n)=Θ(n^p)$ 🠖 $T(2n) = Θ((2n)^p) = 2^pΘ(n^p)=Θ(n^p)$ 이기 때문입니다.

즉, $n$의 오른쪽 ($n$보다 큰 수들)에서 처음으로 만나는 2의 멱수($2^k$)에 대한 함수도 항상 $n$에 대한 함수와 같은 점근 복잡도를 가지므로, $n=2^k$라고 가정해도 점근적 분석의 결과는 동일합니다. 따라서 이런 가정은 일반성을 잃지 않습니다.

물론 모든 점근 복잡도에 대해 위의 논리가 성립하는 것은 아닙니다. 하지만, 적어도 다항식으로 표현되는 복잡도는 이 논리가 성립합니다. 이때 알고리즘의 복잡도 함수를 단조 증가 함수라고 가정하는 것은 크기가 더 큰 입력에서는 크기가 더 작은 입력에서보다 수행시간이 “적어도” 적게 걸리지는 않는다는 가정입니다. 즉, 큰 입력에 대해 수행되는 시간은 더 작은 입력에 대해 수행되는 시간 이상 소요된다는 가정입니다.

이것이 100% 맞는것은 아니지만, 이것 때문에 결과가 왜곡되거나 알고리즘 분석의 질이 떨어지지는 않습니다.

추정 후 증명

추정 후 증명은 식을 보고 점근적 복잡도를 추정한 다음, 그것이 옳음을 귀납적으로 증명하는 방법입니다. 병합 정렬의 점화식 $T(n) ≤ 2T(\frac{n}{2}) + n$의 점근적 복잡도를 추정한 후 증명법을 이용하여 확인해봅시다:

$T(n) ≤ 2T(\frac{n}{2}) + n$의 점근적 복잡도는 $T(n) = O(nlogn)$이다. 즉, 충분히 큰 n에 대해 $T(n) ≤ cnlogn$인 양의 상수 c가 존재한다.

증명:

• 경계조건: $T(2) ≤ c2log2$를 만족하는 c가 존재합니다. (이 때, $log1 = 0$이므로 $T(1) ≤ 1log1$은 불가능하기 때문에 T(2)를 경계조건으로 설정하였습니다. T(2)가 아닌 훨씬 큰 임의의 상수 a에 대해 $T(a) ≤ caloga$를 보여도 상관없습니다.)
• 전개: $\frac{n}{2}$에 대해 $T(\frac{n}{2}) ≤ c(\frac{n}{2})log\frac{n}{2}$를 만족한다고 가정하면,
• $T(n) ≤ 2T(\frac{n}{2}) + n$
            ${≤ 2c(\frac{n}{2})log\frac{n}{2} + n}$
            $= cnlogn - clog2 + n$
            $= cnlogn + ① (-cnlog2 + 1)n$
       ② $≤ cnlogn$
  

최종적으로 ②의 결론을 도출하려면 ①의 항이 음수 (더 정확하게는 0이하)이면 됩니다. 즉, c가 $\frac{1}{log2}$ 이상이기만 하면 됩니다. 충분히 큰 n에 대해 $T(n) ≤ cnlogn$인 상수 c를 잡을 수 있으므로 증명은 완료되었습니다.

추정 후 증명법을 유용하게 사용하려면 우선 추정을 의미 있게 해야 합니다. 너무 여유롭게, 혹은 너무 무리한 추정은 증명이 되지 않습니다.

좋은 추정을 하기 위해서는 먼저 점화식의 모양에 익숙해져야 합니다. 시각적으로 재귀 호출 트리를 그려가면서 추정할 수도 있고, 경험이 많이 쌓이면 식의 모양만 보고도 대략적인 의미있는 추정을 할 수 있는 직관이 생깁니다.

마스터 정리

마스터 정리는 특정한 모양을 가진 재귀식에서 바로 결과를 도출할 수 있는 유용한 정리입니다.

마스터 정리는 다음 형태의 식에 적용된다:

$T(n) = aT(\frac{n}{b}) + f(n)$

즉, “입력의 크기가 n인 문제를 풀기 위해 입력의 크기가 $\frac{n}{b}$인 문제를 a개 풀고, 나머지 f(n)의 오버헤드가 필요한” 알고리즘들이 해당됩니다.

앞서 살펴본 병합정렬이 대표적인 예로, a = b = 2, f(n) = n인 경우입니다.

a ≥ 1, b > 1에 대해 $T(n) = aT(\frac{n}{b})+f(n)$인 점화식에서, $h(n) = n^{log_b a}$라고 할 때, T(n)의 점근적 복잡도는 다음과 같습니다:

• ①. 어떤 양의 상수 ε에 대하여, $\frac{f(n)}{h(n)} = O(\frac{1}{n^ε})$이면, $T(n)=Θ(h(n))$입니다.
• ②. 어떤 양의 상수 ε에 대하여, $\frac{f(n)}{h(n)} = Ω(n^ε)$이고, 어떤 상수 c(< 1)와 충분히 큰 모든 n에 대해 $af(\frac{n}{b})≤cf(n)$이면, $T(n) = Θ(f(n))$입니다.
• ③. $\frac{f(n)}{h(n)} = Θ(1)$ 이면 $T(n) = Θ(h(n)logn)$입니다.
• ①식의 경우, $h(n)$이 더 무거우면 $h(n)$이 수행시간을 결정한다는 의미입니다.
• ②식의 경우, $f(n)$이 더 무거우면 $f(n)$이 수행시간을 결정한다는 의미입니다.
• ③식의 경우, $h(n)$과 $f(n)$이 같은 무게이면 $h(n)$에 $logn$을 곱한 것이 수행시간이 된다는 의미입니다.

마스터 정리의 의미를 좀 더 살펴보자면, $f(n)$은 크기가 n인 문제(최상위 레벨)에서 발생하는 재귀호출 이외의 오버헤드로 “크기가 다른 문제들간의 관계를 반영하는 비용” 입니다. 또, $h(n)$은 반복적인 재귀호출 끝에 마지막으로 크기가 1인 문제를 만나는 횟수입니다.

즉, 재귀호출에 따른 부담이 더 커지면 전체적인 수행시간은 $h(n)$이 결정하고, 관계를 반영하는 오버헤드가 더 커지면 $f(n)$이 결정합니다. 단, $f(n)$은 “가장 상위 레벨”의 오버헤드만을 의미하므로 하위 레벨에서 발생하는 오버헤드는 반영하지 않습니다.

Reference

쉽게 배우는 알고리즘 - 문병로