[알고리즘 분석] 2장. 분할정복법(divide-and-conquer) (4)

1. 큰 정수 계산법

$ u = x \times 10^m + y $, $ v = w \times 10^m + z $

$ u \times v = (x \times 10^m + y) \times (w \times 10^m + z) = xw \times 10^(2m) + (xz + wy) \times 10^m + yz $

x와 y, w와 z는 모두 u와 v의 반인 $ \frac{2}{n} $ 이 된다.

ex)

$ 567,832 = 567 \times 10^3 + 832 $

$ 9,423,723 = 9423 \times 10^3 + 723 $

- 문제: 2개의 큰 정수 u와 v를 곱하라
- 입력: 큰 정수 u와 v, 크기 n
- 출력: prod(u와 v의 곱)
- 알고리즘

large_integer prod(large_integer u, large_integer v){
    large_integer x, y, w, z;
    int n, m;
    
    n = maximum(u의 자리수, v의 자리수);
    if (u == 0 || v == 0) return 0;
    else if (n <= threshold)
        return 일반적인 방법으로 구한 u * v;
    else{
        m = n/2;
        x = u * pow(10, m);
        y = u mod pow(10, m);
        w = v * pow(10, m);
        z = v mod pow(10, m);
        return prod(x, w) * pow(10, 2m) + (prod(x, z) + prod(w, y)) * pow(10, m) + prod(y, z);
    }
}​

[시간복잡도 분석]
- 단위연산: 덧셈, 뺄셈, divide $ 10^3 $, mod $ 10^3 $, $ \times 10^m $
$ n = 2^k $ 라고 가정
단위연산들은 모두 cn

$ W(n) = 4(\frac{n}{2}) + cn $
$ W(s) = 0 $ (s: threshold보다 작거나 같은 문제 크기)
$ W(n) \in \Theta(n^2) $

- 개선된 방법 (prod2)
앞선 알고리즘에서는 xw, xz, yw, yz의 계산으로 4회의 곱셈이 필요했었다. 
r 계산을 추가해서 곱셈을 3회로 만들 수 있다.
$ r = (x + y) \times (w + z) = xw + (xz + yw) + yz $
$ xz + yw = r - xw - yz $
$ (x + y) \times (w + z) $ ... (1)
$ x \times w $ ... (2)
$ y \times z $ ...(3)
으로 총 세번의 곱셈이 필요하게 된다.

[개선된 방법 prod2의 알고리즘]

large_integer prod2(large_integer u, large_integer v){
    large_integer x, y, w, z, r, p, q;
    int n, m;
    n = maximum(u의 자리수, v의 자리수);
    if (u == 0 || v == 0) return 0;
    else if(n <= threshold)
        return 일반적인 방법으로 구한 u * v;
    else{
        m = n/2;
        x = u divide pow(10, m);
        y = u mod pow(10, m);
        r = prod2(x + y, w + z);
        p = prod2(x, w);
        q = prod2(y, z);
        return p*pow(10, 2m) + (r - p - q) * pow(10, m) + q;
    }
}

[prod2의 시간복잡도]
prod2(x+y, w+z): $ \frac{n}{2} \leq 입력크기 \leq \frac{n}{2} + 1 $ n/2에서 x + y가 자리수가 증가할 수 있음
prod2(x, w): $ \frac{n}{2} $
prod2(y, z): $ \frac{n}{2} $

따라서 
$ 3W(\frac{n}{2}) + cn \leq W(n) \leq 3W(\frac{n}{2} + 1) + cn $

$ W(n) \in \Theta(n^{lg3}) $, 약 $ \Theta(n^{1.58}) $

 

2. 임계값 결정

- optimal threshold value를 결정하는 방법

- 문제의 크기가 줄어들면 재귀호출을 수행하는 것보다는 다른 알고리즘을 활용하는 것이 효과적이다.

- 교환정렬을 사용하는 것이 분할하는 것과 같은 효율이 되는 지점을 찾아야 한다.

 

3. 분할 정복 (divide and conquer)을 사용하지 말아야 하는 경우

1) 시간복잡도가 지수 형태로 나올 경우

- 크기가 n인 입력이 2개 이상의 조각으로 분할되며, 분할된 부분들의 크기가 거의 n에 가깝게 되는 경우

2) 시간복잡도가 $ \Theta(n^{lg \ n}) $의 형태로 나올 경우

- 크기가 n인 입력이 n개 이상의 조각으로 분할되며, 분할된 부분의 크기가 $ \frac{n}{c} $인 경우

 

4. 도사정리(The Master Theorem)

 

$ T(n) = a \times T(\frac{n}{b}) + f(n) $의 형태를 이룬다고 할 때,

 

1) 어떤 상수 $ \varepsilon > 0 $에 대해서, 만약 $ f(n) \in O(n^{log_b{a-\varepsilon}}) $이면, $ T(n) \in \Theta(n^{log_ba}) $

 

2) $ f(n) \in \Theta(n^{log_ba})$ 이면, $ T(n) \in \Theta(n^{log_ba} logn) $

 

3) 어떤 상수 $ \varepsilon > 0 $에 대해서, 만약 $ f(n) \in \Omega(n^{log_b{a+\varepsilon}}) $이고, 어떤 상수 c<1과 충분히 큰 모든 n에 대해서 $ a \times f(\frac{n}{b}) \leq c \times f(n) $이면, $ T(n) \in \Theta(f(n)) $이다.