Divide and Conquer
분할 정복으로 불리는 알고리즘으로 디자인 패러다임은 다음과 같다.
- 문제를 여러개의 소문제로 분할한다.
- 재귀적으로 소문제를 정복한다.
- 소문제의 해결책을 합처서 문제를 해결한다.
이미 병합 정렬과 마스터 정리를 통해 많이 접해왔다.분할 정복 알고리즘의 대표적인 예시는 다음과 같다.
- Merge sort
- Binary search
- Powering a number
- Fibonacci numbers
- Matrix multiplication
- Strassen's algorithm
- VLSI tree layout
병합 정렬은 이미 알고 있기에 마스터 정리로 구한 성능만 알고 넘어가자.
Binary Search(이진 탐색)
이진 탐색은 이미 정렬된 배열에서 원소를 찾는 알고리즘으로 이를 Divide conquer로 생각하면 다음과 같다.
- Divide:배열 중간의 요소를 확인한다.
- Conquer:재귀적으로 요소가 포함된 소배열을 찾는다.
- Combine
이진 탐색은 https://kshdevstory.tistory.com/82 에 정리해 놓았다.
이진 탐색 알고리즘의 재귀적 표현은 다음과 같다.
Powering a number
a를 n번만큼 제곱하는 것으로 계산하는 알고리즘으로 N은 이때 정수여야 한다.일반적으로 생각해보면 알고리즘의 성능은
a * a * a ... 로서 O(n)이지만 이를 분할 정복 알고리즘으로 생각해보면 다음과 같다.
n이 짝수,홀수임을 구분하여 지수에 대한 문제로 계속 나눌 수 있다.이를 재귀적으로 접근하면 마스터 정리로 유도가 가능하다.
우선 재귀호출은 한번 이루어지고 문제는 절반으로 나뉘고 병합하는데는 상수시간이 걸리기에 시간 복잡도는 O(lgn)이 된다.
Fibonacci numbers(피보나치 수)
피보나치 수열은 자기 자신과 자신의 전 수를 더한 값이 다음 값이 되는 수열로 재귀적인 정의는 다음과 같다.
피보나치 수를 Bottom-up(상향식 접근)으로 성능을 평가하면 시간 복잡도는 O(n)이 된다.단순하게 재귀적으로 덧셈을 실행했을때의 성능으로 이를 분할 정복 알고리즘으로 접근하면 행렬의 곱을 수행하는 것으로 생각해볼 수 있다.우선 피보나치 수열의 점화식은
F(n) = F(n -1) + F(n-2)이고 이를 행렬 곱으로 나타내면 다음과 같다.
피보나치 수를 거듭제곱으로 구할 수 있기에 시간 복잡도가 O(lg n)이 되어 더 좋은 성능을 나타낸다.
행렬의 곱은 수학적 귀납법을 통해 증명이 가능하다.
Matrix multiplication(행렬의 곱셈)
행렬의 곱을 나타내면 다음과 같다.
행렬의 곱셈을 단순하게 계산하는 방법은 3중 for문을 3번 순회하는 것이다.이럴경우 시간복잡도는 O($n^{3}$)이 된다.
이를 분할 정복 알고리즘으로 생각해보면 행렬의 곱을 2 * 2행렬 기준 8번의 곱셈과 4번의 덧셈으로 계산되는것으로 유도할 수 있다.
재귀적 표현으로 나타내고 마스터정리로 시간 복잡도를 구하면 다음과 같다.
하지만 이는 일반적으로 생각할 수 있는 3중 for문과 시간복잡도에서 차이가 나지 않는다.
Strassen's idea
행렬의 곱셈을 풀이하는 알고리즘으로 8번의 곱셈과정을 7번으로 줄여서 시간 복잡도를 계산할 수 있는 알고리즘이다.
스트라센 알고리즘의 재귀적표현과 시간복잡도는 다음과 같다.
차수를 줄였다는 것에서 큰 의미가 있는 알고리즘이다.