[알고리즘] D&C 기법의 예시와 좋은 pivot이란?

(지난주)
D&C기법? 같은 문제의 더 작은 instance로 recursion 하는 방법.

D&C 알고리즘의 시간 복잡도 분석
1. 점화식을 찾아라
  ( 재귀하는 부분 & 나머지 부분 )  -> T(n) = r*T(n/c)+O(f(n)) 형태 
2. 점화식을 풀어라
  ( Recursion tree , Master Theorem 등)

Mater Theorem
: 점화식이 T(n) = r*T(n/c) + O(f(n)) 형태를 만족할 때만 적용 가능, f(n)과 n^(log c r)을 비교
- f(n) = Ω(n^(logc r+ε)  >> T(n) = O(f(n))
- f(n) = Θ(n^(log c r)    >> T(n) = O(f(n) * log n)
- f(n) = O(n^(log c r-ε)  >> T(n) = O(n^(logc r))

recursion tree 
: T(n) = T(n/3)+T(2n/3)+O(n) 와 같은 예제는 마스터 정리 사용불가, recursion tree를 사용하여 풀자.
             n
        n/3   2n/3
 n/9 2n/9 2n/9 4n/9

해당 트리 안의 노드들의 합을 구하자. 
레벨 별로 합을 구하면 각각의 레벨은 n.
트리의 높이는 logk n이므로 밑은 신경쓰지말고, 레벨*높이 = 총합 = O(n*log n)

-------------------------------------------------------------------------------------------------------------------------------------- 

D&C 알고리즘의 대표적인 예
- Mergesort
- Multiplication

① Multiplication
: n자리의 정수 x와 y가 주어진다. x와 y의 곱셈을 구하자.
 O(n²)의 시간이 걸린다.

② SplitMultiply
(D&C 알고리즘)
n=4                                 //4자리 숫자의 곱
3627 x 9021
= (36x100 + 27)(90x100+21)
= (36x90)x10000 + (36x21+27x90)x100 + 27x21

x와 y를 반으로 잘라서 
x = (10^m)*a + b
y = (10^m)*c + d         //m = [n/2]
 >> 10^(2m)*ac + (10^m)*(bc+ad) + bd

SplitMultiply(x,y,n) :  if n=1  return   x*y  else      m <- n/2     a  <- (x/10)^m     b  <- (y/10)^m  e <- SplitMultiply(a,c,m)  f <- SplitMultipply(b,d,m)  g <- SplitMultiply(b,c,m)  h <- SplitMultiply(a,d,m)  return 10^(2m)*e + 10^m*(g+h)+f

** 10^(2m)은 곱셈이 아니다. 이것은 뒤에 0만 붙이면 되는 쉬프트 연산을 수행할 수 있다.

- Recursion part : n/2 사이즈의 instance를 4번 recursive call
- Non-recursion part : O(n) 사이즈      // 쉬프트, 덧셈 등의 상수 시간
 T(n) = 4*T(n/2)+O(n) >> T(n) = O(n²)

과연 곱셈 문제에 대해서 D&C기법을 통해 n자리 수 두개를 계산하는데 더 빠르게 계산은 안 되는 것인가?
O(n²)이 최선인가? -> Complexity Theory
더 빠른 알고리즘을 만들 수 없었던 이유는 "재귀호출을 네 번 해야 했기 때문"이다.
a*c / b*c / a*d / b*c


③ Fast Multiplication
: 단순 적용보다는 더 나가야 D&C 알고리즘으로 빅오를 줄일 수 있음.

(곱셈 시간복잡도에 대한 역사)
- 1960, Kolmogorov : 곱셈은 O(n²) 보다 빨리는 안될 거야.
- 일주일후, Karatsuba : 반으로 자르고 나면 3번만 재귀 호출할 수 있어.
- 1963, Toom : ㅇㅇ 더 잘게 자르면 더 빠르게 가능함. 
- 1966, Cook : Toom-Cook algorithm
- 1971 : O(n log n loglog n) >> FFT
- 2019 : O(n log n)


④ Matrix Multiplication
행렬 곱셈 >> O(n³)

(D&C 알고리즘)
- 나누자. 이때 mxm 행렬 모양이 되어야 subproblem으로 된다.
  (n/2 x n/2 행렬 >> 더 작은 instance)

A와 B를 네개의 부분 행렬로 나눈다.
n/2 x n/2 행렬 곱셈을 8번 하면 된다.
그 후에 행렬 덧셈과 끼워넣기(복사)로 마무리

T(n) = 8T(n/2)+O(n²) = O(n³)
  // T(n)의 정의 n by n 행렬 두 개의 곱을 계산할 때 걸리는 시간
  // 아까와 같은 곱셈을 8번이나 하기 때문에 O(n³)로 똑같게 된다.

이후, 곱셈을 7번하면 되는 방법을 알아냄. -> T(n) = 7T(n/2)+O(n²) = n^(log2 7)
하지만 아직까진 확실한 행렬 곱셈의 최선의 알고리즘을 구하지 못했다.


⑤ Binary Search
정렬된 문제에서 탐색 문제를 푸는 방법

(D&C 알고리즘)
- A의 중간값을 k와 비교하여 같으면 리턴(비교를 할 때마다 절반으로 줄어 탐색 진행)
- k가 작으면 왼쪽 절반에 대해 탐색 계속
- k가 크면 오른쪽 절반에 대해 탐색 계속

중간값(median)을 k와 비교한 후에, 배열의 절반에 대해서만 "탐색"을 계속
즉, 남은 n/2 크기의 부분 배열에 대한 subproblem을 풀면 문제 해결

// A[a ... b]에서 k를 찾는 알고리즘 int binary_search(int A[], int k, int a, int b){    if (a > b)    return -1;    int mid = (a+b)/2;    if (A[mid] > k)    return binary_search(A, k, a, mid-1);    else if (A[mid] < k)    return binary_search(A, k, mid+1, b);    else    return mid;  }

알고리즘을 재귀호출로 이해하는 것이 쉽다 >> 물론 반복문이 더 빠름

T(n) = T(n/2) +O(1)  // 둘 중 한 번밖에 recurisve call을 안 하기 때문에 T(n/2)이다.
                                  // 절반 이하로 떨어지기 때문에 T(n) <= T(n/2)+O(1) 로도 말할 수 있다.
시간 복잡도는 O(log n)이다.


⑥ Selection
 O(n log n) 시간이 걸린다. >> 정렬로 reduction

QuickSelect(A[1 ... n], k) :    //1부터 시작하는 거에서 조심하자(1<=k<=n 으로 가정)  if n=1       return A[1]  else      Choose a pivot      r <- Partition(A[1 ... n], p)      if         k < r     return QuickSelect(A[1 ... r-1], k)      else if  k > r     return QuickSelect(A[r+1 ... n], k-r)      else                 return A[r]

시간복잡도 분석
: Quicksort와 비슷하지만, Quickselect는 재귀 호출을 한번밖에 안 한다.
  T(n) <= max{T(r-1), T(n-r)} + O(n)

//최악의 경우
r=1이거나 r=n일 때, 최댓값이 되므로 T(n) < T(n-1)+O(n) 이다.
T(n) = O(n²)

좋은 Pivot이란?
: 대략 중간쯤에 위치한 원소(딱 가운데가 아니어도 된다.)
 0 < a < 1에 대해 r=an인 pivot을 항상 고를 수만 있다면 나이스한 선택이다.
 어떻게? T(n) <= max{T(r-1), T(n-r)} + O(n)
              T(n) <= T(max(a, 1-a)n) + O(n) 에서 0<a<1이므로 
              T(n) = O(n)이다.

// 등비수열 점화식
n + 2/3n + 4/9n + ... 쭉 하다 보면
(1 + 2/3 + 4/9 + ...)n 인데 상수값(cn)으로 수렴한다. 따라서 n을 넘지 않는 빅오 O(n)이 나온다.
즉, 중간값과 대략 비슷한 것을 찾을 수 있다면 QuickSelection을 O(n) 시간에 할 수 있다.


좋은 Pivot 구하기
Median-of-Medians 방법
 1. 배열 A[1 ... n]의 원소 n개를 5개씩 묶어 block을 만든다.  
 2. 각 block의 median들을 계산한다.
 3. Median들을 모아 배열 M[1 ... n/5]에 모은 후, 그것들의 median을 pivot으로 사용한다.

if n <= 25  use brue force // 무작정 sort한다. >> O(1)  else  m <- n/5  for i<- to m  M[i] <- MedianOfFive(A[5i-4, 5i]) //median을 구하는 자체 selection  mom <- MomSelect(M[1 ... m], m/2) //mom 값이 pivot이 된다.  r<- Partition(A[1 ... n], mom)  if ... (동일)

Median of Medians(MOM) is a good pivot!
pivot보다 작은 애들이 최소 3n/10개 있다.
pivot보다 큰 애들은 최소 3n/10개 있다. 
★결국 pivot은 3n/10 < r < 7n/10 의 값을 나타낸다.★

재귀 호출을 하지 않은 O(n)이 확실함
재귀호출 한 부분은 두 번의 Recursion이 진행된다. 
- n/5 사이즈에 대해서 한번                 // mom <- MomSelect(M[1 ... m], [m/2]) 
- 최대 7n/10 사이즈에 대해서 한번    //  MomSelect(A[1 ... r-1], k) 혹은 MomSelect(A[r+1 ... n], k-r)
     r-1 >> 3n/10 ~ 7n/10   혹은   n-r >> 3n/10 ~ 7n/10

T(n) <= T(n/5) + T(7n/10) + O(n)

총합 = n + 9/10n + 81/100n + ...
 // 줄어든다. (9/10)ⁿ씩 줄어든다. 
 // (1+9/10+81/100 + ... + )n = 10n = cn = O(n)이다.

이렇게 D&C 알고리즘의 예시들을 보았는데, 여기서 기억할 것은 D&C 기법으로 항상 시간 복잡도를 줄일 수 있는 것은 아니며, 좋은 pivot을 고르면 시간복잡도를 줄일 수 있는 것을 기억하자.