03. 점화식과 점근적 복잡도 분석

* 해당 포스트는 PC환경에 최적화되어 있습니다.

* 쉽게 배우는 알고리즘 개정판 교재로 공부했으며 학교에서 배운 내용과 섞어서 정리한 포스트입니다.

* 저작권 문제는 hjl3066@gmail.com으로 연락 주시면 빠르게 조치하겠습니다.

* 이론이나 예시에서 틀린 부분이 있다면 지적부탁드립니다.

---

점화식

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

동일한 함수가 등호 또는 부등호 양쪽에 나타나는데, 양쪽 함수의 변수 크기가 다르다.

 

아래는 점화식의 예이다.

aₙ = aₙ₋₁ + 2 ← 등차수열

f(n) = f(n - 1) + f(n - 2) ← 피보나치

n! ← 팩토리얼

 

동일한 함수가 양쪽에 나타나고, 함수의 변수 크기가 다르다.

점화식의 예 - 병합정렬 알고리즘

mergeSort(A[], p, r) { // A[p ... r] 정렬
    if (p < r) { // ← 1
        q ← ⌊(p + q) / 2⌋ // p, r의 중간 지점 계산 ← 1
        mergeSort(A, p, q); // 전반부 정렬 ← T(n/2)
        mergeSort(A, q + 1, r); // 후반부 정렬 ← T(n/2)
        merge(A, p, q, r); // 병합 ← C 후처리 시간
    }
}

merge(A[], p, q, r) {
    정렬된 두 배열 A[p ~ q], A[q + 1 ~ r]을 합하여
    정리된 A[p ~ r] 만든다.
}

T(n) = 1 + 1 + (n/2) + (n/2) + C = 2T(n/2) + C + 2, n ≥ 2

T(n) = 2T(n/2) + C, n ≥ 2 ← 점화식

크기가 n인 병합 정렬 시간(T(n))은 크기가 n/2인 병합 정렬을 두 번하는 시간(2T(n/2))과 나머지 오버헤드(C)를 더한 시간이다.

점화식의 점근적 분석법

• 반복 대치
  : 더 작은 문제에 대한 함수로 반복해서 대치
• 추정 후 증명
  : 결론(점근적 복잡도) 추정, 수학적 귀납법 이용
• 마스터 정리
  : 패턴에 따라 공식 이용
  → 형식에 맞는 점화식의 복잡도를 바로 알 수 있다.

반복 대치

- 병합 정렬

$T(n)=2T(\frac{n}{2})+n,n\ge 2$

(n = 2ᵏ라고 가정 ← 모든 상황에서 x, 다항식으로 표현되는 복잡도는 논리가 성립됨)

 

▼ 점화식 반복대치 수행

$T(n)=2(2T(\frac{n}{4})+\frac{n}{2})+n$

= 4T(n/4) + 2n   ←   T(n/4) = 2T(n/8) + n/4

= 4(2T(n/8) + n/4) + 2n

= 8T(n/8) + 3n

= 16T(n/16) + 4n

      ⁝

= 2ᵏT(n/2ᵏ) + kn, n = 2ᵏ, k = log₂n

= nT(1) + n log n

= n + n log n

= O(n log n)

차근차근 수식을 따라오면 어려운 부분이 없다.

다음은 팩토리얼 함수이다. 병합 정렬보다 더 간단하다.

 

- 팩토리얼 함수 연산

T(n) = T(n - 1) + c, T(1) = c, n ≥ 2 (c는 자기 호출 제외한 연산시간)

▼ 점화식 반복대치 수행

T(5) = T(4) + c

= T(3) + 2c

= T(2) + 3c

= T(1) + 4c

= 5c

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

= c + (n - 1)c

= cn

= O(n)

추정 후 증명

여러 경험을 통해 사전 지식을 갖춘 경우, 식의 모양을 보고 점근적 복잡도를 추정한 다음, 그것이 옳음을 수학적 귀납법을 통해 증명하는 방법이다.

 

식의 모양 : T(n) = 2T(n/2) + n, n ≥ 2

추정 : T(n)의 점근적 복잡도는 O(n log n)일 것이다. 즉, T(n) ≤ cn log n

그렇다면 우리가 증명해야 하는 것은 T(n) ≤ cn log n이다.

 

여기서 n에 2와 n/2을 차례로 넣어서 가정해본다.

T(2) ≤ c 2 log₂ 2를 만족하는 c가 존재할 것이다.

그렇다면 n/2에 대해 T(n/2) ≤ c(n/2) log₂ (n/2)을 만족한다고 가정하면,

T(n) = 2T(n/2) + n

T(n) = 2T(n/2) + n ≤ 2 c (n/2) log₂ (n/2) + n이다.

2 c (n/2) log₂ (n/2) + n에서 약분하면 c n log₂ (n/2) + n이 된다.

여기서 로그의 성질을 이용하여(ex. log n/2 = log n - log 2)

c n log₂ (n/2) + n =  c n log₂ n - c n log₂ 2 + n으로 만든다음.

log₂ 2를 1로 바꾸면, c n log₂ n - cn + n로 정리할 수 있다.

T(n) ≤ c n log₂n - cn + n ≤ c n log₂n,

T(n) ≤ c n log n을 만족하는 c가 존재한다.

마스터 정리

T(n) = aT(n/b) + f(n)과 같은 특정한 모양을 가진 점화식은 마스터 정리에 의해 바로 결과를 알 수 있다.

a ≥ 1, b > 1에 대하여  $n^{lo{g}_{b}a}=h(n)$이라 하자.

 

1. 어떤 양의 상수 ε에 대하여 $\frac{f(n)}{h(n)}=O(\frac{1}{n^{\epsilon }})$이면, T(n) = Θ(h(n))이다.
2. 어떤 양의 상수 ε에 대하여 $\frac{f(n)}{h(n)}=\mathrm{\Omega }(\frac{1}{n^{\epsilon }})$이면, 어떤 상수 c( <1 )와 충분히 큰 모든 n에 대해 $af(\frac{n}{b})\le cf(n)$이면 T(n) = Θ(f(n))이다.
3.  $\frac{f(n)}{h(n)}$ =  Θ(1)이면 T(n) =  Θ(h(n) x log n)이다.

다시 말해 양의 상수 ε에 대하여

h(n)이 무거우면 T(n) = Θ(h(n))이고,

f(n)이 무거우면 T(n) = Θ(f(n))이다.

만약, h(n)과 f(n)이 같으면 T(n) = Θ(h(n) x log n)이다. 여기서 x는 곱하기이다.

 

마스터 정리의 예를 보자.

• $T(n)=2T(\frac{n}{3})+c$

 - $a=2,b=3,h(n)=n^{lo{g}_{3}2},f(n)=c$

 - $T(n)=\mathrm{\Theta }(n^{lo{g}_{3}2})$

 

• $T(n)=2T(\frac{n}{4})+c$

 - $a=2,b=4,h(n)=n^{lo{g}_{4}2},n^{\frac{1}{2}}$

 - $T(n)=\mathrm{\Theta }(n)$

 

• $T(n)=2T(\frac{n}{2})+c$

 - $a=b=2,h(n)=n^{lo{g}_{2}2}=n,f(n)=n$

 - $T(n)=\mathrm{\Theta }(nlogn)$