[알고리즘] 분할정복과 알고리즘 - 재귀식의 풀이
동차 선형 재귀식 풀이
Solving Recurrences Using the Characteristic Equation
[ 예시 ]
피보나치 수열의 재귀식 => 동차 선형 재귀식 형태로
$t_n = t_{n-1} = t_{n-2}$, $t_0 = 0$, $t_1 = 1$
=> $t_n - t_{n-1} - t_{n-2} = 0$
[ 동차 선형 재귀식 예제로부터 재귀식 풀이 ]
| 단계 | 내용 |
|---|---|
| 주어진 재귀식 | $t_n - 5t_{n-1} + 6t_{n-2} = 0$ for $n > 1$ $t_0 = 0, t_1 = 1$ |
| 가정 | $t_n = r^n$ |
| 해 | $t_n - 5t_{n-1} + 6t_{n-2} = r^n - 5r^{n-1} + 6r^{n-2} = 0$ $r^n - 5r^{n-1} + 6r^{n-2} = 0 \Rightarrow r^{n-2}(r^2 - 5r + 6) = 0$ $r = 0$, $r = 3$, $r = 2$ |
| 결론 | $t_n = 0$, $t_n = 3^n$,$t_n = 2^n$ |
| 검증 | $t_n = 3^n$, $t_{n-1} = 3^{n-1}$, $t_{n-2} = 3^{n-2}$ $t_n - 5t_{n-1} + 6t_{n-2}$ $3^n - 5(3^{n-1}) + 6(3^{n-2}) = 3^n - 3(3^{n-1}) = 3^n - 3^n = 0$ $t_n = 2^n$가 해인지도 확인함 |
| 일반해 (General Solution) | $t_n = 0$, $t_n = 3^n$, $t_n = 2^n$이 해이므로 재귀식의 일반해는 다음과 같음 $t_n = c_1 3^n + c_2 2^n$(단, $c_1$, $c_2$는 임의의 상수) $c_1 = c_2 = 0$일 경우, $t_n = 0$ 일반해를 완성하려면 초기 조건을 대입하여 $c_1, c_2$ 를 결정 초기 조건 $t_0 = 0$,$t_1 = 1$ |
| 식 정리 | $t_0 = c_1 3^0 + c_2 2^0 = c_1 + c_2 = 0$ $t_1 = c_1 3^1 + c_2 2^1 = 3c_1 + 2c_2 = 1$ $c_1 + c_2 = 0$, $3c_1 + 2c_2 = 1$ |
| 초기 조건을 사용 | $c_1$, $c_2$를 구해서 일반해를 완성하기 위해 |
| 결론적으로 | $c_1 = 1$, $c_2 = -1$ $t_n = 1 \cdot (3^n) - 1 \cdot (2^n) = 3^n - 2^n$ |
| 다른 초기 조건 사용 시 | $t_0 = 1,\quad t_1 = 2$ $t_0 = c_1 3^0 + c_2 2^0 = 1$ $t_1 = c_1 3^1 + c_2 2^1 = 2$ $c_1 + c_2 = 1$ $3c_1 + 2c_2 = 2$ $c_1 = 0,\quad c_2 = 1$ $t_n = 0 \cdot (3^n) + 1 \cdot (2^n) = 2^n$ |
[ 특성 방정식을 이용한 재귀식 풀이 – 예제 1 ]
점화식의 특성 방정식
• 점화식: $5t_n - 7t_{n-1} + 6t_{n-2} = 0$
• 특성 방정식: $5r^2 - 7r + 6 = 0$
| 단계 | 내용 |
|---|---|
| 초기 조건 | $t_0 = 0,\quad t_1 = 1$ |
| 특성 방정식 도출 | 점화식: $t_n - 3t_{n-1} - 4t_{n-2} = 0$ 특성 방정식: $r^2 - 3r - 4 = 0$ |
| 특성 방정식 풀기 | $r^2 - 3r - 4 = (r - 4)(r + 1) = 0$ $r = 4$,$r = -1$ |
| 일반해 구하기 (정리 B.1에 의한) | $t_n = c_1 \cdot 4^n + c_2 \cdot (-1)^n$ |
| 초기 조건을 이용해 상수 $c_1$, $c_2$ 구하기 | 초기 조건: $t_0 = 0 = c_1 \cdot 4^0 + c_2 \cdot (-1)^0 = c_1 + c_2$ $t_1 = 1 = c_1 \cdot 4^1 + c_2 \cdot (-1)^1 = 4c_1 - c_2$ |
| 연립방정식 정리 | $c_1 + c_2 = 0$ $4c_1 - c_2 = 1$ |
| 해 | $c_1 = \frac{1}{5},\quad c_2 = -\frac{1}{5}$ |
| 결론 | 일반해 $t_n = \frac{1}{5} \cdot 4^n - \frac{1}{5} \cdot (-1)^n$ |
[ 특성 방정식을 이용한 재귀식 풀이 – 예제 2 ]
상수계수를 가지는 동차 선형 점화식의 특성방정식은 다음과 같이 정의됨
• 점화식: $a_0t_n + a_1t_{n-1} + … + a_kt_{n-k} = 0$
• 대응되는 특성 방정식: $a_0r^k + a_1r^k-1 + … + a_kr^0 = 0$
• $r^1 = 1$
| 단계 | 내용 |
|---|---|
| 예제 재귀식 | $t_n - t_{n-1} - t_{n-2} = 0,\quad \text{for } n > 1,\quad t_0 = 0,\ t_1 = 1$ |
| 특성 방정식 도출 | $r^2 - r - 1 = 0$ |
| 특성 방정식 해 구하기 | $r = \frac{1 + \sqrt{5}}{2}, \quad r = \frac{1 - \sqrt{5}}{2}$ |
| 일반해 구성 (Theorem B.1에 따라) | $t_n = c_1 \left( \frac{1 + \sqrt{5}}{2} \right)^n + c_2 \left( \frac{1 - \sqrt{5}}{2} \right)^n$ |
| 상수 (c_1, c_2) 초기 조건으로 결정 | 초기 조건: $t_0 = 0$ $c_1 \cdot \left( \frac{1 + \sqrt{5}}{2} \right)^0 + c_2 \cdot \left( \frac{1 - \sqrt{5}}{2} \right)^0 = 1 \cdot c_1 + 1 \cdot c_2 = 0$ $\Rightarrow c_1 + c_2 = 0$ $t_1 = 1$ $c_1 \cdot \left( \frac{1 + \sqrt{5}}{2} \right) + c_2 \cdot \left( \frac{1 - \sqrt{5}}{2} \right) = 1$ |
| 식 정리 및 상수 결정 | $\left( \frac{1 + \sqrt{5}}{2} \right) c_1 + \left( \frac{1 - \sqrt{5}}{2} \right) c_2 = 1$ $c_2 = -c_1$ 를 대입하면 $\left( \frac{1 + \sqrt{5}}{2} \right) c_1 - \left( \frac{1 - \sqrt{5}}{2} \right) c_1 = 1$ $\Rightarrow \left( \frac{\sqrt{5}}{1} \right) c_1 = 1$ $\Rightarrow c_1 = \frac{1}{\sqrt{5}},\quad c_2 = -\frac{1}{\sqrt{5}}$ |
| 최종 일반해 (Final General Solution) | $t_n = \frac{1}{\sqrt{5}} \left( \left( \frac{1 + \sqrt{5}}{2} \right)^n - \left( \frac{1 - \sqrt{5}}{2} \right)^n \right)$ 이 식은 피보나치 수열의 일반항과 동일 |
Multiplicity (중복도)
[ 정의 ]
특성 방정식에서 어떤 근이 몇 번 중복되는지를 표현한 것
$(r - 1)(r - 2)^3 = 0$: $r = 2$가 세 번 중복되므로 중복도는 3
[ 예제1 ]
중복도를 가진 특성 방정식을 사용한 점화식 풀이
| 단계 | 내용 |
|---|---|
| 특성 방정식 도출하기 | 점화식: $t_n - 7t_{n-1} + 15t_{n-2} - 9t_{n-3} = 0 \quad (n > 2)$ $t_0 = 0, \quad t_1 = 1, \quad t_2 = 2$ 특성 방정식: $r^3 - 7r^2 + 15r - 9 = 0$ |
| 특성 방정식 풀기 | $r^3 - 7r^2 + 15r - 9 = (r - 1)(r - 3)^2 = 0$ 중복도: $r = 1$(단일근), $r = 3$(중복도 2의 중근) 해의 형태: $t_n = c_1 \cdot 1^n + c_2 \cdot 3^n + c_3 \cdot n \cdot 3^n$ |
| 정리 B.1에 따라 일반해 구하기 | $t_n = c_1 \cdot 1^n + c_2 \cdot 3^n + c_3 \cdot n \cdot 3^n$ |
| 초기 조건으로 상수 $c_1, c_2, c_3$구하기 | 초기 조건: $t_0 = 0 = c_1 \cdot 1^0 + c_2 \cdot 3^0 + c_3 \cdot (0) \cdot (3^0)$ $t_1 = 1 = c_1 \cdot 1^1 + c_2 \cdot 3^1 + c_3 \cdot (1) \cdot (3^1)$ $t_2 = 2 = c_1 \cdot 1^2 + c_2 \cdot 3^2 + c_3 \cdot (2) \cdot (3^2)$ |
| 식 정리 | $c_1 + c_2 = 0$ $c_1 + 3c_2 + 3c_3 = 1$ $c_1 + 9c_2 + 18c_3 = 2$ |
| 해 | $c_1 = -1, \quad c_2 = 1, \quad c_3 = -\frac{1}{3}$ |
| 최종 일반해 | $t_n = (-1)(1^n) + (1)(3^n) + \left(-\frac{1}{3}\right)(n \cdot 3^n)$ $= -1 + 3^n - n \cdot 3^n \cdot \frac{1}{3} = -1 + 3^n - n \cdot 3^{n-1}$ |
[ 예제2: 중복도를 가진 특성 방정식을 사용한 점화식 풀이 ]
| 단계 | 내용 |
|---|---|
| 점화식 | $t_n - 5t_{n-1} + 7t_{n-2} - 3t_{n-3} = 0 \quad \text{for } n > 2$ $t_0 = 1, \quad t_1 = 2, \quad t_2 = 3$ |
| 특성 방정식 도출하기 | $t_n - 5t_{n-1} + 7t_{n-2} - 3t_{n-3} = 0$ $\Rightarrow r^3 - 5r^2 + 7r - 3 = 0$ |
| 특성 방정식 풀기 | $r^3 - 5r^2 + 7r - 3 = (r - 3)(r - 1)^2 = 0$ 중복도: $r = 3$(단일근), $r = 1$(중복도 2의 중근) |
| 정리 B.1에 따라 일반해 구하기 | $t_n = c_1 \cdot 3^n + c_2 \cdot 1^n + c_3 \cdot n \cdot 1^n$ |
| 초기 조건으로 상수 $c_1, c_2, c_3$ 구하기 | 초기 조건: $t_0 = 1 = c_1 \cdot 3^0 + c_2 \cdot 1^0 + c_3 \cdot 0 \cdot 1^0$ $t_1 = 2 = c_1 \cdot 3^1 + c_2 \cdot 1^1 + c_3 \cdot 1 \cdot 1^1$ $t_2 = 3 = c_1 \cdot 3^2 + c_2 \cdot 1^2 + c_3 \cdot 2 \cdot 1^2$ |
| 위 식 정리 | $c_1 + c_2 = 1$ $3c_1 + c_2 + c_3 = 2$ $9c_1 + c_2 + 2c_3 = 3$ |
| 해 | $c_1 = 0, \quad c_2 = 1, \quad c_3 = 1$ |
| 최종 일반해 | $t_n = 0 \cdot 3^n + 1 \cdot 1^n + 1 \cdot n \cdot 1^n = 1 + n$ |
비동차 선형 점화식 (Nonhomogeneous Linear Recurrences)
[ 정의 (Definition) ]
다음과 같은 형태의 점화식 $a_0 t_n + a_1 t_{n-1} + \cdots + a_k t_{n-k} = f(n)$ 에서, $k$와 $a_i$들은 상수이고 $f(n)$은 0이 아닌 어떤 함수일 때,
이를 상수 계수를 갖는 비동차 선형 점화식 (nonhomogeneous linear recurrence equation with constant coefficients)
• 영 함수(zero function)의 경우: $f(n) = 0$
• 비동차 점화식을 일반적으로 푸는 공식적인 방법은 존재하지 않음
• 하지만, 아래와 같은 일반적인 특수한 경우에는 풀이법이 있음:
$a_0 t_n + a_1 t_{n-1} + \cdots + a_k t_{n-k} = b^n p(n)$
$b$는 상수이며 $p(n)$은 $n$에 대한 다항식(polynomial)
$t_n - 3t_{n-1} = 4^n (8n + 7) \quad \Rightarrow \quad k = 1, \, b = 4, \, p(n) = 8n + 7$
[ 예제 1 ]
$t_n - 3t_{n-1} = 4^n \Rightarrow k = 1, \, b = 4, \, p(n) = 1$
$t_n - 3t_{n-1} = 4^n(n > 1), t_0 = 0, t_1 = 4$
| 단계 | 설명 |
|---|---|
| 점화식에서 $n$을 $n - 1$로 치환 | $t_{n-1} - 3t_{n-2} = 4^{n-1}$ |
| 식을 4로 나눔 | $\frac{t_n}{4} - \frac{3t_{n-1}}{4} = 4^{n-1}$ |
| 다음 두 식을 빼서 $4^{n-1}$ 항 제거 | $\frac{t_n}{4} - \frac{7t_{n-1}}{4} + 3t_{n-2} = 0$ |
| 동차 점화식으로 만들기 위해 4를 곱함 | $t_n - 7t_{n-1} + 12t_{n-2} = 0$ |
| 특성 방정식 | $t_n = r^n \Rightarrow r^2 - 7r + 12 = (r - 3)(r - 4) = 0$ |
| 일반해 | $t_n = c_1 \cdot 3^n + c_2 \cdot 4^n$ |
| 해의 초기 조건 적용 | $t_0 = 0$, $t_1 = 4$ $t_n = 4^{n+1} - 4 \cdot 3^n$ |
주의 사항 (Notice)
$t_n = c_1 \cdot 3^n + c_2 \cdot 4^n$
• $c_1 \cdot 3^n$: 동차 점화식의 특성 방정식에서 유도된 항
• $c_2 \cdot 4^n$: 비동차 항 $4^n$에서 유도된 항
다항식 $p(n)$의 차수: 다항식 $p(n)$의 차수는 $n$의 최고차항이다.
| Polynomial $p(n)$ | Degree |
|---|---|
| $3n^2 + 4n - 2$ | 2 |
| $5n + 7$ | 1 |
| $8$ | 0 |
[ 비동차 점화식 예제 2 풀이 ]
$t_n - 3t_{n-1} = 4^n (2n + 1) \quad \text{for } n > 1$ $t_0 = 0, \quad t_1 = 12$
| 단계 | 설명 |
|---|---|
| 동차식에서 유도한 특성 방정식 | $t_n - 3t_{n-1} = 0 \Rightarrow r^1 - 3 = 0$ |
| 비동차 항으로부터 얻은 항 | $(r - b)^{d+1} = (r - 4)^{1+1} = (r - 4)^2$ |
| 위 항들로부터 특성 방정식을 구성 | $(r - 3)(r - 4)^2 = 0$ |
| 이 방정식을 풀면 | $r = 3$, $r = 4$ (중복도 2) |
| 일반해 | $t_n = c_1 3^n + c_2 4^n + c_3 n 4^n$ |
| 그러나 주어진 초기 조건은 2개뿐 | $t_0 = 0, t_1 = 12$ |
| $t_2$는 점화식을 사용하여 계산 | $t_2 - 3t_1 = 4^2(2 \cdot 2 + 1) \Rightarrow t_2 = 116$ |
| 일반해 구하기 | 초기 조건 $t_0 = 0$, $t_1 = 12$, $t_2 = 116$를 사용하여 일반해를 구하면 $t_n = 20 \cdot 3^n - 20 \cdot 4^n + 8n \cdot 4^n$ |
[ 비동차 선형 점화식 예제 3 풀이 ]
$t_n - t_{n-1} = n - 1 \quad (n > 0), \quad t_0 = 0$
| 단계 | 설명 |
|---|---|
| 동차식에서 유도한 특성 방정식 | $t_n - t_{n-1} = 0 \Rightarrow r^1 - 1 = 0$ |
| 비동차 항에서 유도된 항 | $(r - 1)^{1+1}$ |
| 오른쪽 항 $n - 1 = 1^n(n^1 - 1)$ 로부터 | $b = 1, d = 1$ |
| 두 항을 곱하여 얻는 특성 방정식 | $(r - 1)(r - 1)^2 = (r - 1)^3$ $r = 1$의 중복도 3 해를 갖는 방정식 |
| 정리 B.2에 따라 일반해는 | $t_n = c_1 \cdot 1^n + c_2 n \cdot 1^n + c_3 n^2 \cdot 1^n$ $= c_1 + c_2 n + c_3 n^2$ |
| 두 개의 추가 초기 조건 계산 | $t_1 = t_0 + 1 - 1 = 0 + 0 = 0$ $t_2 = t_1 + 2 - 1 = 0 + 1 = 1$ |
| 초기 조건을 사용하여 일반해 완성 | $t_n = \frac{n(n-1)}{2}$ |
[ 비동차 선형 점화식 예제 4 풀이 ]
$t_n - 2t_{n-1} = n + 2^n \quad (n > 1), \quad t_1 = 0$
| 단계 | 설명 |
|---|---|
| 동차식에서 유도한 특성 방정식 | $t_n - 2t_{n-1} = 0 \Rightarrow r^1 - 2 = 0$ |
| 비동차 항에서 유도된 항 | $(r - 1)^{1+1}, (r - 2)^{0+1}$ |
| → 항 분석 | $n = (1^n) n^1 \Rightarrow b = 1, d = 1$ |
| 정리 B.3을 통한 특성 방정식 도출 | 동차 항: $r^1 - 2 = 0$ 비동차 항: $(r - 1)^2$, $(r - 2)^1$ |
| 결합하여 | $(r - 2)(r - 1)^2(r - 2) = (r - 2)^2(r - 1)^2$ |
변수 치환을 이용한 점화식 풀이
[ 예제 1 ]
$T(n) = T\left(\frac{n}{2}\right) + 1$ (단, $n > 1$, $n$은 $2$의 거듭제곱), $T(1) = 1$
| 단계 | 설명 |
|---|---|
| 아래와 같이 점화식을 변형 | $n = 2^k \Rightarrow k = \log_2 n$ |
| 점화식에 $n = 2^k$를 대입 | $T(2^k) = T\left(\frac{2^k}{2}\right) + 1 = T(2^{k-1}) + 1$ $t_k = T(2^k)$로 두면,$t_k = t_{k-1} + 1$ |
| 정리 B.3에 따라 해는 | $t_k = c_1 + c_2 k$ |
| 원래 점화식의 일반해를 얻기 위해 | ① $T(2^k) = t_k = c_1 + c_2 k$ ② $k = \log_2 n$ 대입 $T(n) = c_1 + c_2 \log_2 n$ |
| 초기 조건 $T(1) = 1$을 이용하면 | $T(n) = 1 + \log_2 n$ |
[ 예제 2 ]
$T(n) = 7T\left(\frac{n}{2}\right) + 18\left(\frac{n}{2}\right)^2, \quad T(1) = 0$
$n = 2^k \Rightarrow k = \log_2 n$
| 단계 | 설명 |
|---|---|
| $n = 2^k$를 대입하면 | $T(2^k) = 7T(2^{k-1}) + 18(2^{k-1})^2$ $t_k = 7t_{k-1} + 18(2^{k-1})^2 = 7t_{k-1} + 18 \cdot 4^{k-1}$ $= 7t_{k-1} + 4^k \cdot \left(\frac{18}{4}\right)$ |
| 정리 B.3에 따라 | $t_k = c_1 \cdot 7^k + c_2 \cdot 4^k$ |
| 원래 점화식의 일반해 구하기 | $T(2^k) = t_k = c_1 \cdot 7^k + c_2 \cdot 4^k$ |
| $k = \log_2 n$ 대입 | $T(n) = c_1 \cdot n^{\log_2 7} + c_2 \cdot n^2$ |
| 초기 조건 $T(1) = 0$을 대입 | $T(n) = 6n^{\log_2 7} - 6n^2 \approx 6n^{2.81} - 6n^2$ |
Substitution(대입법)을 이용한 재귀식 풀이
[ 예제 1 ]
$t_n = t_{n-1} + n \quad \text{(for } n > 1) t_1 = 1$
| 단계 | 설명 |
|---|---|
| 귀납법과 반대처럼, $n$부터 1까지 거꾸로 시작 | $t_n = t_{n-1} + n$ $t_{n-1} = t_{n-2} + n - 1$ $t_{n-2} = t_{n-3} + n - 2$ $\vdots$ $t_2 = t_1 + 2$ $t_1 4= 1$ |
| 각 등식을 대입해서 $t_n$을 구함 | $t_n = t_{n-1} + n$ $= t_{n-2} + (n - 1) + n$ $= t_{n-3} + (n - 2) + (n - 1) + n$ $\vdots$ $= t_1 + 2 + \cdots + (n - 2) + (n - 1) + n$ $= 1 + 2 + \cdots + (n - 1) + n$ $= \sum_{i=1}^n i = \frac{n(n+1)}{2}$ |
[ 예제 2 ]
$t_n = t_{n-1} + \frac{2}{n} (n > 1), t_1 = 0$
| 단계 | 설명 |
|---|---|
| 귀납법과 반대로 $n$에서 1로 진행 | $t_n = t_{n-1} + \frac{2}{n}$ $t_{n-1} = t_{n-2} + \frac{2}{n - 1}$ $t_{n-2} = t_{n-3} + \frac{2}{n - 2}$ $\vdots$ $t_2 = t_1 + \frac{2}{2}$ $t_1 = 0$ |
| 각 등식을 대입해서 $t_n$ 구하기 | $t_n = t_{n-1} + \frac{2}{n}$ $= t_{n-2} + \frac{2}{n - 1} + \frac{2}{n}$ $= t_{n-3} + \frac{2}{n - 2} + \frac{2}{n - 1} + \frac{2}{n}4$ $\vdots$ $= t_1 + \frac{2}{2} + \cdots + \frac{2}{n - 2} + \frac{2}{n - 1} + \frac{2}{n}4$ $= 0 + \cdots + \frac{2}{n - 2} + \frac{2}{n - 1} + \frac{2}{n}4$ $= 2 \sum_{i=2}^n \frac{1}{i} \approx 2 \ln n$ |
시간 복잡도
n이 어떤 양의 상수 b의 거듭제곱일 때의 결과를 일반적인 n으로 확장하기
[ 네 가지 시간 복잡도 함수 ]
| 종류 | 설명 |
|---|---|
| 엄격히 증가하는 함수 (Strictly Increasing) | 항상 증가 |
| 비감소 함수 (Nondecreasing) | 절대 감소하지 않음 |
| 비비감소 함수가 아님 (Not Nondecreasing) | 오르내림 반복 |
| 궁극적으로 비감소하는 함수 (Eventually Nondecreasing) | 일정 시점 이후로는 증가 또는 유지 |
[ strictly increasing ]
💡 정의
복잡도 함수 $f(n)$이 항상 $n$이 증가함에 따라 커지면 이를 엄격히 증가함(strictly increasing) 이라고 한다
• 즉, $n_1 > n_2$ 이면, $f(n_1) > f(n_2)$
• log₂n, n, n log n, n², 2ⁿ 등 (단, n ≥ 0일 때)
[ non decreasing ]
💡 정의
복잡도 함수 $f(n)$이 n이 증가함에 따라 절대 감소하지 않으면, 이를 비감소함(nondecreasing) 이라고 한다
• 즉, $n_1 > n_2$ 이면, $f(n_1) ≥ f(n_2)$
• 대부분의 시간 복잡도 함수는 비감소 함수
[ Not Nondecreasing ]
💡 예시
n이 2의 거듭제곱일 때의 f(n)
• 예: $2^3 = 8$, $2^4 = 16$ 사이에서 결론을 내릴 수 없음
• 하지만 만약 $f(n)$이 비감소 함수라면 $f(8) ≤ f(n) ≤ f(16)$ 이라는 범위가 성립 (8 ≤ n ≤ 16 구간에서)
• 결론: 비감소가 아닌 함수는 일반적인 시간 복잡도를 판단할 수 없음
[ Eventually Nondecreasing ]
💡 정의
복잡도 함수 $f(n)$은 어떤 시점 이후로 절대 작아지지 않으면 결국에는 감소하지 않는다(eventually nondecreasing)라고 부른다
즉, 어떤 $N$이 존재하여 $n_1 > n_2 > N$일 때는 항상 $f(n_1) \geq f(n_2)$
• ‘Eventually Nondecreasing’ 조건을 통해 $n4$이 $4b$의 거듭제곱일 때 일반 $n$으로 확장
💡 smooth function(부드러운, 급격하게 바뀌지 않는)
1) 다음 조건을 만족하는 복잡도 함수 $f(n)$
• 결국 증가하지 않음(eventually nondecreasing)
• $f(2n) \in \Theta(f(n))$: 입력이 2배가 되어도 함수의 차수가 크게 달라지지 않음
2) Smooth 함수의 예시
• $\lg n, n, n \lg n, n^k$
• $\lg(2n) = \lg 2 + \lg n \in \theta(\lg n)$
smooth function의 성질을 이용한 확장 이론
1) 정수 $b \geq 2$일 때,
• $f(n)$: smooth 복잡도 함수
• $T(n)$ eventually nondecreasing 복잡도 함수
2) $T(n) \in \Theta(f(n))$ (단, $n$이 $b$의 거듭제곱일 때)이 성립하면
• 일반적으로 $T(n) \in \Theta(f(n))$도 성립
• 위 정리는 $\Theta$뿐만 아니라 $O$, $\Omega$, 소문자 $o$ 표기에도 동일하게 적용
[ 예제 ]
$T(n) = T\left( \left\lfloor \frac{n}{2} \right\rfloor \right) + 1$ (단, $n > 1$), $T(1) = 1$
1) 시간 복잡도
• $T(n) = \lg n + 1 \in \Theta(\lg n)$ ($n$이 2의 거듭제곱일 때)
• 2의 거듭제곱 사이의 값들에 대한 결론은 없음
2) 귀납법으로 $T(n)$이 eventually nondecreasing임을 증명
$n \geq 2$에 대해, $ 1 \leq k \leq n$이면 $T(k) \leq T(n)$
| 단계 | 내용 |
|---|---|
| 귀납 기본 단계 | $T(1) = 1$ $T(2) = T\left(\left\lfloor \frac{2}{2} \right\rfloor\right) + 1 = T(1) + 1 = 2$ $T(1) \leq T(2)$ |
| 귀납 가정 | 모든 $m \leq n$에 대해, $k < m$이면 $T(k) \leq T(m)$ |
| 귀납 단계 | • 가정에 따라 $k < n$이면 $T(k) \leq T(n)$ • 보여야 할 것: $T(n) \leq T(n+1)$ • 다음의 참인 명제 사용: $\left\lfloor \frac{n}{2} \right\rfloor \leq \left\lfloor \frac{n+1}{2} \right\rfloor \leq n$ • 귀납 가정에 따라: $T\left(\left\lfloor \frac{n}{2} \right\rfloor\right) \leq T\left(\left\lfloor \frac{n+1}{2} \right\rfloor\right)$ |
| 결론적으로 | $T(n) = T\left(\left\lfloor \frac{n}{2} \right\rfloor\right) + 1 \leq T\left(\left\lfloor \frac{n+1}{2} \right\rfloor\right) + 1 = T(n+1)$ |
Master Theorem
Master Theorem
1) 복잡도 함수 $T(n)$이 결국 비감소 함수이고 다음을 만족한다고 가정하자:
• $T(n) = aT\left(\frac{n}{b}\right) + cn^k$ (단, $n > 1$, $n$은 $b$ 의 거듭제곱
• $T(1) = d$
2)
• $b \geq 2$, $k \geq 0$는 정수 상수
• $a, c, d$는 $a > 0, c > 0, d \geq 0$인 상수 \(T(n) \in \begin{cases} \Theta(n^k) & \text{if } a < b^k \\ \Theta(n^k \log n) & \text{if } a = b^k \\ \Theta(n^{\log_b a}) & \text{if } a > b^k \end{cases}\)
3) 재귀식의 진술에서 다음 중 하나로 대체
• 재귀식: $T(n) = aT\left(\frac{n}{b}\right) + cn^k$
• 대체 1: $T(n) \leq aT\left(\frac{n}{b}\right) + cn^k$
• 대체 2: $T(n) \geq aT\left(\frac{n}{b}\right) + cn^k$
4)결과: B.5는 각각 “빅 O” 또는 $\Omega$를 사용하여 성립하며, $\Theta$는 대체 가능
[ Example 1 ]
1) $T(n)$이 결국 비감소 함수이고 다음을 만족한다고 가정하자
• $T(n) = 8T(n/4) + 5n^2$ (단, $n > 1$, $n$은 4의 거듭제곱)
• $T(1) = 3$
2)정리 B.5에 따라, $8 < 4^2$ 이므로, $T(n) \in \Theta(n^2)$
[ Example 2 ]
1) $T(n)$이 결국 비감소 함수이고 다음을 만족한다고 가정하자
• $T(n) = 9T(n/3) + 5n^1$ (단, $n > 1$, $n$ 은 $3$의 거듭제곱)
• $T(1) = 7$
2) 정리 B.5에 따라, $9 > 3^1$ 이므로, $T(n) \in \Theta(n^{\log_3 9}) = \Theta(n^2)$
Extended Theorem
1) 복잡도 함수 $T(n)$이 결국 비감소 함수이고 다음을 만족한다고 가정하자:
• $T(n) = aT(n/b) + cn^k$ (단, $n > 2$, $n$은 $b$ 의 거듭제곱)
• $T(s) = d$
2) 정리 B.5의 결과가 여전히 성립
• 여기서 $s$는 $b$의 거듭제곱인 상수
• $b \geq 2$, $k \geq 0$은 정수 상수
• $a, c, d$는 $a > 0, c > 0, d \geq 0$인 상수
[ Example 1 (Extended Theorem) ]
$T(n)$이 결국 비감소 함수이고 다음을 만족한다고 가정하자:
$T(n) = 8T(n/2) + 5n^3$ (단, $n > 64$, $n$은 $2$의 거듭제곱)
$T(64) = 200$
정리 B.6에 따라, $8 = 2^3$이므로, $T(n) \in \Theta(n^3 \log n)$
Strassen’s Matrix Multiplication
행렬 곱셈에서 곱셈의 수에 대한 시간 복잡도는 $T(n) = n^3$으로 주어지며, 여기서 $n$은 행과 열의 수
[ 행렬 곱셈 문제 ]
\[\begin{bmatrix} c_{11} & c_{12} \\ c_{21} & c_{22} \end{bmatrix} = \begin{bmatrix} a_{11} & a_{12} \\ a_{21} & a_{22} \end{bmatrix} \times \begin{bmatrix} b_{11} & b_{12} \\ b_{21} & b_{22} \end{bmatrix}\] \[\begin{aligned} m_1 &= (a_{11} + a_{22})(b_{11} + b_{22}) \\ m_2 &= (a_{21} + a_{22})b_{11} \\ m_3 &= a_{11}(b_{12} - b_{22}) \\ m_4 &= a_{22}(b_{21} - b_{11}) \\ m_5 &= (a_{11} + a_{12})b_{22} \\ m_6 &= (a_{21} - a_{11})(b_{11} + b_{12}) \\ m_7 &= (a_{12} - a_{22})(b_{21} + b_{22}) \end{aligned}\]두 개의 $2 \times 2$ 행렬 A와 B의 곱 $C$를 구한다고 가정
• Strassen의 방법은 7개의 곱셈과 18개의 덧셈/뺄셈 필요
• 반면 직관적인 방법은 8($n^3$)개의 곱셈과 4($n^2$)개의 덧셈/뺄셈
그렇다면 곱 $C$는 다음과 같이 주어진다:
\[C = \begin{bmatrix} m_1 + m_4 - m_5 + m_7 & m_3 + m_5 \\ m_2 + m_4 & m_1 + m_3 - m_2 + m_6 \end{bmatrix}\]$2 \times 2$행렬의 경우 Strassen의 방법은 아무런 가치가 없다?
[ 더 고차원 행렬에서 Strassen의 방법 ]
\[A_{11} = \begin{bmatrix} a_{11} & a_{12} \cdots a_{1,n/2} \\ a_{21} & a_{22} \cdots a_{2,n/2} \\ \vdots & \\ a_{n/2,1} & \cdots a_{n/2,n/2} \end{bmatrix}\]$M_1 = (A_{11} + A_{22})(B_{11} + B_{22})$
$M_2$부터 $M_7$까지 계산
그후 더하기 $C_{11} = M_1 + M_4 - M_5 + M_7$
[ Strassen 알고리즘에서의 부분 행렬로의 분할 ]
\[\begin{bmatrix} C_{11} & C_{12} \\ C_{21} & C_{22} \end{bmatrix} = \begin{bmatrix} A_{11} & A_{12} \\ A_{21} & A_{22} \end{bmatrix} \times \begin{bmatrix} B_{11} & B_{12} \\ B_{21} & B_{22} \end{bmatrix}\] \[A = \begin{bmatrix} 1 & 2 & 3 & 4 \\ 5 & 6 & 7 & 8 \\ 9 & 1 & 2 & 3 \\ 4 & 5 & 6 & 7 \end{bmatrix} \quad B = \begin{bmatrix} 8 & 9 & 1 & 2 \\ 3 & 4 & 5 & 6 \\ 7 & 8 & 9 & 1 \\ 2 & 3 & 4 & 5 \end{bmatrix}\]행렬들을 부분 행렬로 나눈다:
\[\begin{bmatrix} C_{11} & C_{12} \\ C_{21} & C_{22} \end{bmatrix} = \begin{bmatrix} 1 & 2 & 3 & 4 \\ 5 & 6 & 7 & 8 \\ 9 & 1 & 2 & 3 \\ 4 & 5 & 6 & 7 \end{bmatrix} \times \begin{bmatrix} 8 & 9 & 1 & 2 \\ 3 & 4 & 5 & 6 \\ 7 & 8 & 9 & 1 \\ 2 & 3 & 4 & 5 \end{bmatrix}\]Strassen의 방법을 사용하여 부분 행렬을 정복
\[M_1 = (A_{11} + A_{22})(B_{11} + B_{22}) \\ = \left( \begin{bmatrix} 1 & 2 \\ 5 & 6 \end{bmatrix} + \begin{bmatrix} 2 & 3 \\ 6 & 7 \end{bmatrix} \right) \times \left( \begin{bmatrix} 8 & 9 \\ 3 & 4 \end{bmatrix} + \begin{bmatrix} 9 & 1 \\ 4 & 5 \end{bmatrix} \right)\] \[= \begin{bmatrix} 3 & 5 \\ 11 & 13 \end{bmatrix} \times \begin{bmatrix} 17 & 10 \\ 7 & 9 \end{bmatrix}\]행렬들이 충분히 작아졌을 때, 표준 방식으로 곱한다:
사실 더 해도 되지만 여기까지하도록~~~
[ 시간복잡도 분석 ]
💡 모든 경우의 곱셈 수에 대한 시간 복잡도 분석
• 두 개의 $n \times n$ 행렬이 있고 $n>1$일 때, 알고리즘은 정확히 7번 호출
• 각 호출마다 $(n/2) \times (n/2)$크기의 행렬이 전달되고, 최상위 단계에서는 곱셈이 수행되지 않음
• $T(n) = 7T\left(\frac{n}{2}\right)$, (단, $n > 1$ 이고 $n$ 은 $2$의 거듭제곱, $T(1) = 1$
• 해결: $T(n) = n^{\log_2 7} \approx n^{2.81} \in \Theta(n^{2.81})$
💡 모든 경우의 덧셈/뺄셈 수에 대한 시간 복잡도 분석
• 두 개의 $(n/2) \times (n/2)$ 행렬이 덧셈 또는 뺄셈될 때, 각 원소에 대해 $(n/2)^2$번의 연산이 수행
• 수식:
$T(n) = 7T\left(\frac{n}{2}\right) + 18\left(\frac{n}{2}\right)^2$, (단, $n > 1$이고 $n$ 은 2의 거듭제곱), $T(1) = 0$
• 해결: $T(n) = 6n^{\log_2 7} - 6n^2 \approx 6n^{2.81} - 6n^2 \in \Theta(n^{2.81})$
Slide 1: 홀수 개의 행 또는 열일 때
- 0으로 패딩
- ( n \times n ) 행렬을 곱하는 두 알고리즘의 비교
| 기본 알고리즘 (Standard Algorithm) | Strassen 알고리즘 | |
|---|---|---|
| 곱셈 (Multiplications) | ( n^3 ) | ( n^{2.81} ) |
| 덧셈/뺄셈 (Additions/Subtractions) | ( n^3 - n^2 ) | ( 6n^{2.81} - 6n^2 ) |
Slide 2: 큰 정수의 산술 연산 (Arithmetic with Large Integers)
- 문제
- 정수의 크기가 컴퓨터의 정수 표현 하드웨어 한계를 초과할 경우, 산술 연산을 해야 한다고 가정하자. 결과에서 모든 유효 숫자를 유지해야 한다면, 부동소수점 표현으로 전환하는 것은 아무 의미가 없다.
- 큰 정수를 표현하는 방법은 정수 배열을 사용하는 것이다.
- 예: 543.127
[ \text{S[6]} = 5, \quad \text{S[5]} = 4, \quad \text{S[4]} = 3, \quad \text{S[3]} = 1, \quad \text{S[2]} = 2, \quad \text{S[1]} = 7 ]
- 양의 정수와 음의 정수를 모두 표현하려면 부호를 위한 상위 배열 슬롯 하나만 예약하면 된다. 이 슬롯에 0을 넣으면 양의 정수, 1을 넣으면 음의 정수로 표현할 수 있다.
- 산술 연산에서의 문제!!!
Slide 3: 큰 정수에 대한 산술 연산의 해결책
- n자리 정수를 약 ( n/2 ) 자리 정수 두 개로 나누기
일반적으로, 정수 ( u )의 자릿수가 ( n )이라면, 우리는 이를 다음과 같이 두 정수로 나눈다 (하나는 ( \lceil n/2 \rceil ), 다른 하나는 ( \lfloor n/2 \rfloor )):
[ u = x \cdot 10^m + y ]
- 여기서 ( x ): ( \lceil n/2 \rceil ) 자릿수, ( y ): ( \lfloor n/2 \rfloor ) 자릿수
- 이 표현에서 10의 지수 ( m )은 다음과 같다:
[ m = \left\lfloor \frac{n}{2} \right\rfloor ]
두 개의 n자리 정수 ( u, v )가 있다고 하면,
[
u = x \cdot 10^m + y
v = w \cdot 10^m + z
]
곱 ( uv )는 다음과 같이 주어진다:
[
uv = (x \cdot 10^m + y)(w \cdot 10^m + z)
= xw \cdot 10^{2m} + (xz + wy) \cdot 10^m + yz
]
Slide 4: 큰 정수에 대한 산술 연산의 해결책 (계속)
- 예제: ( 567,832 \times 9,423,723 )
Divide (분할):
[
567,832 = 567 \cdot 10^3 + 832 \quad \text{(각각 3자리)}
9,423,723 = 9423 \cdot 10^3 + 723 \quad \text{(각각 4자리, 3자리)}
]
Conquer (정복):
[ 567,832 \times 9,423,723 = (567 \cdot 10^3 + 832)(9423 \cdot 10^3 + 723) ] [ = 567 \cdot 9423 \cdot 10^6 + (567 \cdot 723 + 9423 \cdot 832) \cdot 10^3 + 832 \cdot 723 ]
Slide 5: 큰 정수 곱셈 알고리즘
- 문제: 큰 정수 ( u ), ( v ) 두 개를 곱하라
- 입력: 큰 정수 ( u ), ( v )
- 출력: ( u \times v )의 곱인 ( \texttt{prod} )
large_integer prod(large_integer u, large_integer v)
{
large_integer x, y, w, z;
int n, m;
n = maximum(number of digits in u, number of digits in v)
if (u == 0 || v == 0)
return 0;
else if (n <= threshold)
return u × v obtained in the usual way;
else {
m = ⌊n/2⌋;
x = u divide 10^m; y = u rem 10^m;
w = v divide 10^m; z = v rem 10^m;
return prod(x,w) × 10^{2m} + (prod(x,z) + prod(w,y)) × 10^m + prod(y,z);
}
}
다른 내용도 필요하시면 알려주세요!
좋습니다! 아래는 마지막 슬라이드 세트에 대한 직역 번역본입니다.
Slide 1: 큰 정수 곱셈 알고리즘 분석
-
( x, y, w, z )는 모두 정확히 ( n/2 ) 자리수를 가진다.
이는 곱셈 함수prod에 대한 네 개의 재귀 호출마다 입력 크기가 ( n/2 )라는 의미이다.
( m = n/2 )이므로, 덧셈, 뺄셈, ( \div 10^m ), ( \bmod 10^m ), ( \times 10^m ) 연산은 모두 선형 시간 복잡도를 가진다. -
점화식 (Recurrence equation)
[ W(n) = 4W\left(\frac{n}{2}\right) + cn \quad \text{(for } n > s,\; n \text{ is a power of 2)} ] [ W(s) = 0 ]
- 해결(solution)
[ W(n) \in \Theta(n^{\log_2 4}) = \Theta(n^2) ]
Slide 2: 정수 곱셈 알고리즘의 개선 (곱셈 줄이기)
- 곱셈 항들을 줄이기 위한 방법:
[ \text{기존: } \quad xw,\; xz,\; yw,\; yz ]
- 만약 아래처럼 설정한다면:
[ r = (x + y)(w + z) = xw + (xz + yw) + yz ]
- 그러면 다음이 성립한다:
[ xz + yw = r - xw - yz ]
- 따라서 다음의 세 값만 계산하면 된다:
[ r = (x + y)(w + z),\quad xw,\quad yz ]
Slide 3: 정수 곱셈 알고리즘 개선 (계속) - 알고리즘 설명
- 문제: 큰 정수 ( u, v )를 곱하라
- 입력: 큰 정수 ( u ), ( v )
- 출력: ( u \times v )의 곱 ( \texttt{prod2} )
Slide 4: 개선된 정수 곱셈 알고리즘
large_integer prod2 (large_integer u, large_integer v)
{
large_integer x, y, w, z, r, p, q;
int n, m;
n = maximum(number of digits in u, number of digits in v);
if (u == 0 || v == 0)
return 0;
else if (n <= threshold)
return u × v obtained in the usual way;
else {
m = ⌊n/2⌋;
x = u divide 10^m; y = u rem 10^m;
w = v divide 10^m; z = v rem 10^m;
r = prod2(x + y, w + z);
p = prod2(x, w);
q = prod2(y, z);
return p × 10^{2m} + (r - p - q) × 10^m + q;
}
}
Slide 5: 개선된 큰 정수 곱셈 알고리즘의 분석
- ( x + y )의 자리수 수에 대한 예시들:
| ( n ) | ( x ) | ( y ) | ( x + y ) | ( x + y )의 자리 수 |
|---|---|---|---|---|
| 4 | 10 | 10 | 20 | ( 2 = \frac{n}{2} ) |
| 4 | 99 | 99 | 198 | ( 3 = \frac{n}{2} + 1 ) |
| 8 | 1000 | 1000 | 2000 | ( 4 = \frac{n}{2} ) |
| 8 | 9999 | 9999 | 19998 | ( 5 = \frac{n}{2} + 1 ) |
Slide 6: 개선된 큰 정수 곱셈 알고리즘 분석 (계속)
-
알고리즘 내 ( x + y )의 자리수 예시 (계속)
- ( n )이 2의 거듭제곱이면 ( x, y, w, z )는 모두 ( n/2 ) 자리수이다.
[
\frac{n}{2} \leq \text{digits in } x+y \leq \frac{n}{2} + 1
\frac{n}{2} \leq \text{digits in } w+z \leq \frac{n}{2} + 1
]
- 결론적으로 (Consequently)
| 호출 함수 | 입력 크기 (Input Size) |
|---|---|
| ( \texttt{prod2}(x + y,\; w + z) ) | ( \frac{n}{2} \leq \text{입력 크기} \leq \frac{n}{2} + 1 ) |
| ( \texttt{prod2}(x,\; w) ) | ( \frac{n}{2} ) |
| ( \texttt{prod2}(y,\; z) ) | ( \frac{n}{2} ) |
Slide 7: 개선된 큰 정수 곱셈 알고리즘 분석 (계속)
-
( x + y ) 자리수 예시 계속
-
점화식 (Recurrence equation)
[ 3W\left(\frac{n}{2}\right) + cn \leq W(n) \leq 3W\left(\frac{n}{2} + 1\right) + cn \quad \text{for } n > s,\; n \text{ is a power of 2} ] [ W(s) = 0 ]
- 해결 (Solution)
[ W(n) \in \Omega(n^{\log_2 3}) ]
모든 슬라이드의 직역이 완료되었습니다! 혹시 요약이나 다시 정리된 노트가 필요하시면 알려주세요.