2. Divide-and-conquer algorithms

분할 정복 알고리즘은 문제를 같은 형태의 더 작은 부분문제로 나누고 이 부분문제를 푼 뒤 이 답을 적절히 결합시킨다. 예를 알아보자.

2.1. Multiplication

(a+bi)(c+di)의 곱은 3개의 곱으로 가능하다: ac-bd+((a+b)(c+d) – ac-bd)i. 이는 재귀적으로 적용할 수 있기 때문에 유용하다. 아직은 O(n^{2})인데, 다음 방법을 쓰면 더 줄일 수 있다.

function multiply(x, y)
Input: n-bit positive integers x and y
Output: Their product

if n=1: return xy
x_L, x_R = leftmost ceil(n/2), rightmost floor(n/2) bits of x
y_L, y_R = leftmost ceil(n/2), rightmost floor(n/2) bits of y

P_1 = multiply(x_L, y_L)
P_2 = multiply(x_R, y_R)
P_3 = multiply(x_L + x_R, y_L + y_R)
return P_1 × 2^n + (P_3 - P_1 - P_2) × 2^(n/2) + P_2

이는 O(n^{1.59})이다. 부분 문제 수가 3^{k}이기 때문이다. 그래서 O(n^{\lg 3})이 된다. 이것이 없으면 O(n^{\lg 4}) = O(n^{2})이다. 실제 구현에서는 프로세서가 2의 승수 단위로 계산을 하므로 큰 의미는 없다. 더 잘할 수도 있다.

2.2. Recurrence relations

재귀 식의 수행 시간을 결정하는 다음 정리가 있다: T(n) = aT(\lceil \frac{n}{b} \rceil) + O(n^{d}), a > 0, b > 1, d ≥ 0이면 d > \log_{b} a이면 T(n) = O(n^{d}), d = \log_{b} a이면 T(n) = O(n^{d} \log n), d < \log_{b} a이면 T(n) = O(n^{\log_{b} a})이다.

2.3. Mergesort

다음은 병합 정렬이다.

function mergesort(a[1..n])
Input: An array of numbers a[1..n]
Output: A sorted version of this array

if n > 1:
    return merge(mergesort(a[1..floor(n/2)]), mergesort(a[floor(n/2)+1..n]))
else:
    return a
function merge(x[1..k], y[1..l])
if k=0: return y[1..l]
if l=0: return x[1..k]
if x[1] ≤ y[1]:
     return x[1] . merge(x[2..k], y[1..l])
else:
     return y[1] . merge(x[1..k], y[2..l])

수행 시간은 O(n \log n)이다. 실제 작업은 병합 과정에서 이루어진다. mergesort는 반복적으로 수행될 수도 있다. 이는 다음과 같이 하면 된다.

function iterative-mergesort(a[1..n])
Input: elements a_1, ..., a_n to be sorted

Q = [] (empty queue)
for i = 1 to n:
    inject(Q, [a_i])
while |Q| > 1:
    inject(Q, merge(eject(Q), eject(Q)))
return eject(Q)

2.4. Medians

중위값은 50% 퍼센타일의 값이다. 이는 어떨 때 평균보다 더 좋은 대표성을 가진다. 정렬해서 구하면 O(n \log n)이지만 이는 느리다. 더 잘할 수는 없나?

A randomized divide-and-conquer algorithm for selection

다음과 같이 하면 된다.

selection(S, k) = selection(S_L, k) if k ≤ |S_L|, v if |S_L| < k ≤ |S_L| + |S_R|, selection(S_R, k – |S_L| – |S_v|) if k > |S_L| + |S_v|.

수행 시간은 O(n)이 된다. 하지만 이를 위해서는 v를 중위값으로 골라야 한다. 어떻게 이 모순을 해결할까?

Efficiency analysis

최악의 경우엔 \Theta(n^{2})가 된다. 무작위로 v를 선택하면 어떻게 되나? 그러면 평균 수행 시간은 O(n)이다.

2.5. Matrix multiplication

행렬곱은 O(n^{3})이다. 스트라센의 행렬곱을 쓰면 O(n^{\lg 7}) \simeq O(n^{2.81})이다.

2.6. The fast Fourier transform

다항식을 곱하는 것은 \Theta(d^{2})이다. 더 잘할 수는 없나?

2.6.1. An alternative representation of polynomials

다음의 성질을 이용한다: d차 다항식은 d + 1개의 다른 점에 의해 유일하게 결정된다. 이 점들로 변환한 뒤 점들을 곱하는 것은 선형 시간이 걸리므로 이를 다시 역변환하면 된다. 기본적으론 이것도 \Theta(n^{2})이지만, 더 잘할 수 있다.

2.6.2. Evaluation by divide-and-conquer

짝수 계수와 홀수 계수로 나눠서 잘 계산할 수만 있다면 O(n \lg n)으로 만들 수 있다. 하지만 어떻게 해야 할까? 복소수를 쓰면 된다.

2.6.3. Interpolation

\omega = e^{\frac{2 \pi i}{n}}을 원시근으로 놓고 1, \omega, \cdots, \omega^{n-1}의 점들을 쓰면 된다.

A matrix reformulation

방데르몽드 행렬 M으로 나타내면 평가는 M을 곱하는 것이고 외삽은 M의 역행렬을 곱하는 것이다.

Interpolation resolved

M_{n}(\omega)^{-1} = \frac{1}{n} M_{n}(\omega^{-1)의 성질을 잘 이용하면 역행렬 구하기를 O(n^{3})에 할 필요가 없다. 또한, M의 각 열들은 직교한다.

2.6.4. A closer look at the fast Fourier transform

FFT는 효율적으로 병렬화가 가능하다.

답글 남기기

아래 항목을 채우거나 오른쪽 아이콘 중 하나를 클릭하여 로그 인 하세요:

WordPress.com 로고

WordPress.com의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Google photo

Google의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Twitter 사진

Twitter의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Facebook 사진

Facebook의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

%s에 연결하는 중