[알고리즘] D&C 기법, Recursion tree와 Master Theorem

//저번 시간
Recursion
: simple and delegate!
 자기 자신으로 reduce 하는 전략
Reduction >> 다른 문제의 알고리즘을 활용한다.

Recursive algorithms
: Correctness : induction으로 증명한다.
Time Complexity Analysis : 점화식을 구한다.

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

//이번 시간
1. Divide and Conquer //패턴(결국엔 recursion)
   알고리즘 설계, 문제 해결 기법
   n이 주어지면 -1씩 줄어드는 것이 아닌 더 덩어리가 크게 나누어진다.
2. D&C (divide and conquer) 기법을 활용하여 알고리즘 설계하기
3. 시간복잡도 분석
   점화식에 대한 시간 복잡도 -> Recursion tree

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

(Mergesort)
// divide and conquer의 대표적인 알고리즘
1. 배열이 둘로 나눠지면
2. 각각을 정렬
3. 정렬된 두 subarray를 합친다.

- 가장 중요한 부분은 종료조건. // n>1
- 같은 조건에 대한 더 작은 조건을 해결함. >> 부분 문제(subproblem)

(Quicksort)
// Mergesort와 조금 다른점은 pivot을 골라서 partition을 한다(divide 하는 과정)
1. pivot을 고른다.
2. pivot을 기준으로 작은 것과 큰것들을 분류 >> divide 하는 부분
3. 두개를 정렬

- 부분문제를 해결하고 나면 아무 할 일도 없다.
- pivot을 어떤것을 구하느냐에 따라서 알고리즘이 달라질 수 있다.


Divide and Conquer 전략 >> "나누고 때려잡고 수습하기"
1. divide : 주어진 instance를 더 작은 instance로 나눈다.
                  instance사이즈가 n/2, n/3 같은 경우가 많음. >> n*c (c<1)
2. Delegate : 재귀호출 
3. Combine : small instance가 답이 아니므로 이것들을 합쳐서 답을 도출해냄.

** 입력으로 주어진 사이즈가 constance threshold보다 작아서 상수 시간만큼 걸린다면, brute force(무식하게) 풀어라.

Analyzing the running time >> setting up and solving a recurrence(점화식)
이러한 점화식은 대게 recursion tree를 사용해서 풀 수 있다.

■1. SUM ■ >> 시간복잡도 : O(n)
- input : 자연수 n
- output : 1+2+ ... + n

sum 슈도코드 - D&C알고리즘

D&C알고리즘
- sum(1, n/2)     // 원래 문제에서 더 작은 사이즈라고 말할 수 있음.
- sum(n/2+1, n) // 원래 문제에서 더 작은 사이즈가 아님. (1부터 돌아가는 게 아니기 때문에.)

1+2+ ... + n-1+n 에서 n을 반으로 나눠서 계산하면
>> 2(1+2+ ... + n/2) + (n/2)² 이다.

따라서 시간 복잡도는 n -> n/2 -> n/4 -> n/8 이 되므로 O(log2 n) 이다.

홀수인 경우 
>> n-1이 짝수라고 생각하면 된다.
>> sum(n-1)+n

sum(n) :
if   n=1      return 1
if   n is even then    return 2*sum(n/2)+(n/1)²
else  return sum(n-1)+n

시간복잡도는 빅오 O(log2 n) 즉 O(log n)이다. 
-------------


■2. MAX ■
★빅오 O(n) >> 배열을 다 훑어야 하기 때문에 O(n) 보다 더 빠른 알고리즘이 존재하지 않다. 
만약에 배열이 존재하는데, 이것이 모두 동일한 값일 경우에는 이것 또한 n번 돌아야 하는가? >> 즉 빅오 O(n)인가? O(1)인가?

1. 나눴을 때의 각 덩어리가 n보다 작아야한다.
2. 원래 문제에 대한 instance가 되어야한다.

n인 배열에서 사이즈가 절반인 n/2가 두개 생긴다.
각각의 배열에서 MAX값을 정한다. 그럼 M1, M2 중에서 하나가 MAX값이 될 것이다.

max 슈도코드 - D&C 알고리즘

// c언어 에서는 배열 존재 X. 포인터(주소) 개념이기 때문에   범위를 지정해서 값을 구함. 
max2(int A[], int a, int b){ // a<x<b 안에서 최댓값 찾기

if(a==b)       return A[a];
int mid = (a+b)/2;
int m1 = max2(A, a, mid);
int m2 = max2(A, mid+1, b);
if(m1 > m2)
    return m1;
else return m2;
}

재귀 호출이 들어가는 시간복잡도
"재귀 호출을 어디서 하는지" & 그 외 나머지 부분에서 걸리는 시간(상수 시간:  O(1))
>> T(n) = 2T(n/2)+O(1)
>> 위의 식을 풀면 시간복잡도는 상수개 O(n)가 나온다.

홀수인 경우에서는 무시해도된다.
-------------

■Recursion Tree■
- 재귀알고리즘의 실행 과정에서 재귀 호출을 계속할 것이다.
- 재귀호출이 한 번만 있으면 ㄱㅊ
- 재귀호출을 두 번 이상 호출하게 되면?

excluding recursive calls >> 재귀가 아닌 나머지 연산들에서 걸리는 시간

각 노드의 value를 정해야 한다. >> value의 합 >> 전체 알고리즘 시간 복잡도
 ( Sum of the values of all nodes = overall running time of the algorithm )


((트리 설명))
- learf의 개수 n개 // 결국 나눠지고 나눠져서 배열의 개수임.
- leaf가 아닌 노드 들은 n-1개 //토너먼트라고 생각하면 n-1번의 경기를 한다고 생각하면 된다.
- leaves+ leaf가 아닌 노드들 = 2n-1 // binary tree의 성질
 >> T(n) = 2*T(n/2)+O(1)

★★Master Theorem★★
T(n) = r*T(n/c) + O(f(n)) 을 만족한다면,
- f(n) = Ω(n^(logc r+ε)) >> T(n) = O(f(n))
- f(n) = Θ(n^(logc r) * log^k n >> T(n) = O(f(n)* log n)
- f(n) = O(n^(logc r-ε)) >> T(n) = O(n^logc r)


일반화해서 얘기하자면 D&C 알고리즘은 
사이즈가 n/c 인 부분 문제들을 r 개의 재귀호출을 통해 풀어낸다.
(그 예로, Mergesort에 대해서 n/2에 대해서 재귀 호출을 2번 했다.)
재귀 호출을 하지 않는 부분에 대해서 O(f(n))이다. // 나머지

T(n) = r*T(n/c) + O(f(n)) 이 존재한다면,
- L = tree depth = logc n // 높이
- leaves = r^L = r^logc n = n^ logc r //말단의 개수

(결과만)
기준 : n^logc r
- if f(n)이 클 때   // n의 몇 승보다 빠르게 증가할 경우, T(n) = O(f(n))
    재귀호출한 시간이 너무 커서, f(n)이 먹어버림
- if f(n)이 중간일 때   // n, T(n) = O(f(n)*log n)
  f(n)=n^(logc n) 일 경우도 존재하고, f(n)=n*log n 형태로 존재할 경우도 해당된다.
- if f(n)이 작을 때  // n이 기준상보다 더 작은 경우, T(n) = O(n^logc r)
  비재귀가 재귀 호출한 시간보다 상대적으로 느리게 증가한 경우 비 재귀가 먹어버림
  따라서 연산의 개수를 세야하므로 n의 log승이 되는 것이다.

★중요. f(n)에 log가 있을 경우, log를 붙여서 비교함 >> 그 뒤 세타인지, 빅오인지, 빅오 메가인지 판단★


((연습))
T(n) = 2*T(n/2) + O(n) // r=2, c=2, logc r = 1
  f(n) = n
세타 >> case 2번
T(n) = O(n*logn)
-----------
T(n/2)+O(n) //r=1, c=2, logc r = log2 1= 0
 f(n) = n
빅오 >> case1번
T(n) = n
-------
T(n) = T(n/2)+O(1) // r=1, c=2, logc r = 0
 n^0 =1,  f(n)=1
case 2번
T(n) = O(log n)
-------
T(n) = 4T(n/2)+O(n) //r=4, c=2, logc r = 2
 n^(log2 4)=n^2, f(n)=n
case 3번
T(n)=O(n²)
-------
4// recursion tree를 사용하여 품 > T(n) = O(n log n)
-------
5// quick sort에서 최악의 경우 이러한 점화식이 나온다. T(2)는 상수이다. >> T(n) = T(n-1)+O(n)
   a마스터 정리를 사용 X . recursion tree를 사용하여 풀 수 있음.
-------


시간복잡도를 푸는 방법 >> Recursion Tree
1. 일단 점화식부터 찾아라!
2. 그 다음에 점화식을 풀어라!

Mergesort
T(n) = 2*T(n/2)+O(n)
>> n/2배열들을 두 번 호출하니까 2T(n/2)가 된다.  >> binary tree
  각 노드의 value가 달라진다. O(n) = c*n
어떻게 계산하냐?
 레벨별로 합 : 트리의 높이만큼 n이 있다. >> log2 n
 따라서 n * log2 n 이므로 O(n log n)