[Discrete Mathematics] 점화 관계(recurrence relation)와 알고리즘 분석에 대한 응용

---

점화 관계

 

점화 관계는 수열을 선행 항으로 표현한다. 점화식이라고도 한다.

수열 $ a_0, a_1, \dots $ 에 대한 점화 관계는 $ a_n $ 과 그 앞의 항들인 특정 $ a_0, a_1, \dots, a_{n-1} $ 과의 관계를 나타내는 식이다. 이 수열 $ a_0, a_1, \dots $ 에 대한 초기 조건은 명시적으로 유한 개의 수열 항에 주어진 값들이다.

예를 들어 피보나치 수열을 점화 관계로 나타낸다면, $ f_n = f_{n-1} + f_{n-2} $ $ (n \geq 3) $ 이고, 초기 조건은 $ f_1 = 1, f_2 = 1 $ 이다.

이러한 점화 관계는 재귀적 알고리즘 및 수학적 귀납법과 관련되어 있다.

예를 들어 피보나치 수열의 재귀적 알고리즘을 구현한다면 다음과 같고, 이를 수학적 귀납법으로 증명 가능하기 때문이다.

Fibonacci(n) {
    if (n == 1 or n == 2) {
        return 1
    }
    return Fibonacci(n-1) + Fibonacci(n-2)
}

대표적 예제로 하노이 탑 문제도 있다. 하노이 탑은 판자 위 세 개의 막대가 있고, 구멍 뚫린 서로 다른 크기의 원판이 $ n $ 개 있을 때 이 원판들을 다른 막대로 옮기는 퍼즐이다. 단 원판은 막대에 모두 쌓여 있어야 하고, 막대에 쌓인 원판은 크기가 큰 순서대로 아래에 있어야 한다. 보통 1번 막대에 모든 원판이 쌓여있는 상태에서 조건을 지키면서 3번 막대로 모든 원판을 옮기는 최소한의 이동 횟수를 구하는 것이 하노이 탑 문제이다.

초기 조건은 원판이 한 장만 있는 경우이다. 원판이 한 장만 있다면 그냥 원하는 막대로 옮기면 된다. 즉 한 번에 옮길 수 있다. 만약 원판이 한 장 이상, $ n $ 개 있다면, 먼저 상위 $ n-1 $ 개의 원판을 남아있는 2번 막대에 옮기고, 가장 아래 원판을 3번 막대에 옮긴 다음 2번 막대에 있는 원판들을 다시 3번 막대로 옮기면 된다. $ n - 1 $ 개의 원판을 옮기는 방법은 다시 $ n - 2 $ 개의 원판을 옮기고... 이런 식으로 재귀적으로 반복된다.

즉 식으로 정리한다면 $ c_n = 2c_{n-1} + 1 $ $ ( n > 1 ) $ 이고, 초기 조건은 $ c_1 = 1 $ 이다. (자세한 하노이 탑 예제 풀이는 링크를 참고)

이러한 방식으로 수열을 점화 관계와 초기 조건으로 나타낼 수 있다. 그리고 다시 이를 일반항으로 나타낼 수도 있을텐데, 이를 점화식을 푼다고 한다. 점화 관계의 일반항에 대한 명시적 공식을 찾기 위해선 반복법과 상계수 선형 동차 점화 관계를 이용한다.

 

---

반복법을 통한 점화 관계 풀이

 

반복법으로 수열 $ a_0, a_1, \dots $ 에 대한 점화 관계를 풀 때에는 $ a_n $ 을 선행 항 몇 개로 표현하는 데에 점화 관계를 이용한다. 점화 관계를 순차적으로 사용하여 각각의 $ a_{n-1} , \dots $ 을 해당하는 선행 항 몇 개로 치환하는 것을 명시적 공식이 얻어질 때까지 반복하는 것이다.

예를 들어 점화 관계가 $ a_n = a_{n-1} + 3 $ 이고, 초기 조건이 $ a_1 = 2 $ 라 해보자. 그렇다면 다음과 같이 순차적으로 풀어낼 수 있다.

$ a_n = a_{n-1} + 3 = ( a_{n-2} + 3) + 3 = a_{n-2} + 2 \cdot 3 = (a_{n-3}+3) + 2 \cdot 3 = a_{n-3} + 3 \cdot 3 $

따라서 일반적으로 $ a_n = a_{n-k} + k \cdot 3 $ 이다. $ k = n-1 $ 로 두면 $ a_n = a_1 + (n-1) \cdot 3 = 2 + 3(n-1) $ 이다.

 

---

상계수 선형 동차 점화 관계를 통한 점화 관계 풀이

 

$ k $ 차 상계수 선형 동차 점화 관계는 $ a_n = c_1 a_{n-1} + c_2 a_{n-2} + \cdots + c_k a_{n-k} $ $ (c_k \neq 0 ) $ 와 같은 형태이다. $ k $ 개의 초기 조건, $ a_0 = C_0, a_1 = C_1 , \cdots, a_{k-1} = C_{k-2} $ 이 설정된 $ k $ 차 상계수 선형 동차 점화 관계는 수열 $ a_0, a_1, \dots $ 을 유일하게 정의한다.

이때 여러 정리가 활용될 수 있다.

$ a_n = c_1 a_{n-1} + c_2 a_{n-2} $ 를 2차 상계수 선형 동차 점화 관계라 할 때, $ S $ 와 $ T $ 가 이 점화 관계의 해라면 $ U = bS + dT $ $ (b, d \in \mathbb{R} ) $ 도 이 점화 관계의 해이다. 만일 $ r $ 이 $ t^2 - c_1 t - c_2 = 0 $ 의 근이라면 $ n = 0, 1, \dots $ 에 대한 수열 $ r^n $ 은 이 점화 관계의 해이다.

$ S $ 와 $ T $ 가 이 점화 관계의 해이므로 $ S_n = c_1 S_{n-1} + c_2 S_{n-2} $, $ T_n = c_1 T_{n-1} + c_2 T_{n-2} $ 이다. $ U_n = bS_n + dT_n = c_1(b S_{n-1} + dT_{n-1}) + c_2 ( bS_{n-2} + dT_{n-2}) = c_1U_{n-1} + c_2 U_{n-2} $ 이므로 $ U $ 는 이 점화 관계의 해이다.

$ a_n = c_1 a_{n-1} + c_2 a_{n-2} $ 를 2차 상계수 선형 동차 점화 관계라 할 때, $ a $ 가 이 점화 관계에 의해 정의된 수열이고, $ a_0 = C_0 , a_1 = C_1 $ 이며, $ r_1, r_2 (r_1 \neq r_2) $ 가 $ t^2-c_1t-c_2=0 $ 의 근이라면 $ a_n = br_1^n + dr_2^n $ $ ( n = 0, 1, \dots) $ 이 성립되는 상수 $ b $ 와 $ d $ 가 존재한다.

만약 $ U_n = br_1^n + dr_2^n $ 이라 하면 $ U $ 는 이 점화 관계의 해여야 한다. $ a_0 = C_0, a_1 = C_1 $ 인 초기 조건을 만족시키기 위해서 다음이 성립해야 한다.

$ U_0 = b + d = C_0 $, $ U_1 = br_1 + dr_2 = C_1 $

이때 $ r_1 \times (b+d) - (br_1+dr_2) : d(r_1-r_2) = r_1 C_0 - C_1 $ 이고 $ r_1 \neq r_2 $ 이므로 $ d $ 에 대해 풀 수 있다. 마찬가지로 $ r_2 \times (b+d) - (br_1+dr_2) $ 로부터 $ b $ 에 대해 풀 수 있다.

$ b $ 와 $ d $ 에 대한 이러한 선택으로 $ U_0 = C_0, U_1 = C_1 $ 이 된다.

$ a $ 를 $ a_n = c_1 a_{n-1} + c_2 a_{n-2} $ 과 $ a_0 = C_0 , a_1 = C_1 $ 로 정의한 수열이라 하면 $ U $ 역시 이를 만족하기 때문에 $ U_n = a_n $, $ (n = 0, 1, \dots) $ 가 된다.

예를 들어 피보나치 수열의 명시적 공식을 찾을 때 활용할 수 있다. 피보나치 수열은 $ f_n = f_{n-1} + f_{n-2} $ 이고, 초기 조건이 $ f_1 = 1, f_2 = 1 $ 이었다. 이를 활용해 $ t^2 - t - 1 = 0 $ 이고, 따라서 $ t = (1 \pm \sqrt{5} ) / 2 $ 이다. 이를 다시 대입하여 보면 $ f_n = b\frac{1 + \sqrt{5} }{2}^n + d \frac{1 - \sqrt{5} }{2} ^n $ 이다. 따라서 다음이 성립한다.

$$ \begin{cases} f_1 = b \frac{1+ \sqrt{5} }{2} + d \frac{1 - \sqrt{5} }{2} = 1 \\ f_2 = b \frac{1 + \sqrt{5} }{2}^2 + d \frac{1 - \sqrt{5} }{2}^2 = 1 \end{cases} $$

따라서 $ b = 1/\sqrt{5} $ 이고 $ d = - 1/\sqrt{5} $ 이다. 그러므로 일반항은 다음과 같다.

$$ f_n = \dfrac{1}{\sqrt{5}} \left( \dfrac{1+\sqrt{5}}{2} \right) ^n - \dfrac{1}{\sqrt{5}} \left( \dfrac{1-\sqrt{5}}{2} \right) ^n $$

만약 $ a_n = c_1 a_{n-1} + c_2 a_{n-2} $ 가 2차 상계수 선형 동차 점화 관계이고, $ a_0 = C_0, a_1 = C_1 $ 이라 할 때, $ t^2 - c_1 t - c_2 = 0 $ 의 두 근이 $ r $ 로 같다면 $ n = 0, 1, \dots $ 에 대해서 $ a_n = br^n + dnr^n $ 인 상수 $ b $ 와 $ d $ 가 존재한다.

수열 $ nr^n $, $ (n = 0, 1, \dots) $ 이 $ a_n = c_1 a_{n-1} + c_2 a_{n-2} $ 의 해임을 보이면 된다.

$ r $ 이 중근이므로 $ t^2 - c_1 t - c_2 = (t-r)^2 = t^2 - 2rt - r^2 $ 이다. 그러므로 $ c_1 = 2r, c_2 = -r^2 $ 이다.

$ c_1 ((n-1)r^{n-1}) + c_2 ((n-2) r^{n-2}) = 2r ((n-1)r^{n-1}) - r^2 ((n-2) r^{n-2}) = r^n (2(n-1)-(n-2)) = nr^n $ 이다.

 

---

알고리즘 분석에 응용

 

• 선택 정렬(selection sort)

선택 정렬 알고리즘은 수열의 먼저 가장 큰 원소를 가진 위치를 선택하여 그것을 맨 뒤로 옮긴 다음 나머지 항목을 재귀적으로 정렬하는 방식으로 입력받은 수열을 비내림차순으로 정렬한다.

입력: $ s $ (수열), $ n $ (수열의 길이)
출력: $ s $ (비내림차순으로 정렬된 수열)

selection_sort(s, n) {
    if (n == 1) {
        return s
    }
    max_index = 1
    for i = 2 to n {
        if (s[i] > s[max_index]) {
            max_index = i
        }
    }
    swap(s[n], s[max_index])
    return selection_sort(s, n-1)
}

 

$ b_n $ 을 $ n $ 개의 항목 정렬에 필요한 알고리즘에서의 비교(s[i] > s[max_index]) 횟수라 할 때 이를 반복법으로 분석할 수 있다.

$ b_n = b_{n-1} + n - 1 \\ = (b_{n-2} + n - 2) + (n-1) = b_{n-2} + (n-2) + (n-1) \\ = (b_{n-3} + n - 3) +(n-2)+(n-1) = b_{n-3} + (n-3) + (n-2)+(n-1) \\ \vdots \\ = b_1 + 1 + 2 + \cdots + (n-2) + (n-1) \\ = 0 + 1 + 2 + \cdots + (n-2) + (n-1) \\ = \dfrac{(n-1)n}{2} = \mathcal{\Theta} (n^2) $

 

• 이진 탐색(binary search)

이진 탐색은 정렬된 수열에서 원하는 값을 찾아 인덱스를 반환한다. 만약 찾지 못한다면 정해진 값을 반환한다. 일반적으로는 0이나 NULL을 반환한다. 이 알고리즘은 분할정복(divide-and-conquer)법을 사용한다.

입력: $ s $ (비내림차순으로 정렬된 수열), $ key $ (찾고자 하는 값), $ i $ (시작 인덱스), $ j $ (끝 인덱스)
출력: $ index $ (찾고자 하는 값의 인덱스)

binary_search(s, i, j, key) {
    if (i > j) {
        return NULL
    }
    k = floor((i+j)/2)
    if (key == s[k]) {
        return k
    }
    else if (key < s[k]) {
        j = k - 1
    }
    else {
        i = k + 1
    }
    return binary_search(s, i, j, key)
}

이진 탐색에서 최악의 경우 소요 시간을 $ n $ 항 수열에 대해서 최악의 경우로 알고리즘이 호출되는 횟수로 정의하고 이를 $ a_n $ 으로 표현한다 가정하자. 초기 조건 $ a_1 = 2 $ 이다. $ n > 1 $ 일 때, 원래 수열의 왼쪽의 크기는 $ \lfloor (n-1)/2 \rfloor $ 이고, 오른쪽은 $ \lfloor n/2 \rfloor $ 이며, 최악의 경우는 더 긴 수열에서 나타나기에 총 호출 횟수는 $ a_{\lfloor n/2 \rfloor } $ 이 된다. 즉 $ a_n = 1 + a_{\lfloor n/2 \rfloor } $ 이다.

만약 $ n = 2^k $ 이면 다음과 같다.

$ a_n = a_{2^k} = 1 + a_{2^{k-1}} \\ = 1 + (1 + a_{2^{k-2}}) = 2 + a_{2^{k-2}} \\ \vdots \\ = k+a_{2^0} = k+2 = \lg n + 2 $

따라서 임의의 $ n $ 은 $ 2^{k-1} < n \leq 2^k $ 이다.

수열 $ a $ 는 비감소 순열이므로 $ a_n \leq a_{2^k} = \lg 2^k +2 = \lg 2^{k-1} + 3 < \lg n + 3 $ 이고 따라서 $ a_n = \mathcal{O} (\log n) $ 이다. 또한 $ a_n \geq a_{2^{k-1}} = \lg w^{k-1} + 2 = \lg 2^k + 1 > \lg n $ 이고 따라서 $ a_n = \mathcal{\Omega}(\lg n) $ 이다.

결론적으로 $ a_n = \mathcal{\Theta}(\lg n) $ 이다.