분할정복

:문제를 나눌 수 없을 때까지 나누어서 각각을 풀면서 다시 합병하여 문제의 답을 얻는 알고리즘

*재귀호출과 다른 것은 같은 크기의 부분 문제를 나누는 것.

1)구성

-divide:문제를 더 작은 문제로 분할하는 과정
-merge:각 문제에 대해 구한 답을 원래 문제에 대한 답으로 병합하는 과정
-base case:더이상 답을 분할하지 않고 곧장 풀 수 있는 매우 작은 문제

2)조건

: 둘이상의 부분 문제로 나누는 자연스러운 방법이 있어야하고,원래 문제의 답을 계산하는 효율적인 방법이 있어야 한다.

3)장단점

-장점:작업을 더 빠르게 처리해 준다. 병렬적으로 문제를 해결하고 효율적이다.
-단점:함수를 재귀적으로 호출한다는 점에서 함수 호출로 인한 오버헤드 발생하며 스택에 다양한 데이터를 보관하고 있어야하므로 스택 오버플로우가 발생하거나 과도한 메모리 사용하게 된다.

4)예시

수열의 빠른 합과 행렬의 빠른 제곱

fastSum(n) = 1 +2 + ... .+ n
= (1+2+.... n/2) + ( (n/2+1) + .... n )
= (1+2+.... n/2) + ( (n/2+1) +(n/2+2)+(n/2+3) .... + (n/2+n/2) ) // 각각에 n/2를 밖으로 빼면
= (1+2+.... n/2) + (1 + 2+ .... n/2) +n/2n/2
= 2fastSum(n/2) +n^2/4

와같이 짝수일 때에는 n/2까지만 계산해도 구할수 있다. 하지만 홀수일 때에는 n-1까지 구해야한다.