분할정복
> 1. 주어진 문제의 입력을 나눌수 없을 때까지 두개이상 작은 문제로 순환적으로 분할
2. 작은 문제들을 각각 해결
3. 그해를 결합하여 원래 문제의 해를 구하는 방식
분할 > 정복 > 결합
이진탐색 : n개 -> n/2 + (n/2) 분할 -> (n/4) + n/4 + (n/4 + n/4) 분할한 것의 일부만 사용
합병정렬 : n개 -> n/2 + n/2 분할 -> n/4 + n/4 + n/4 + n/4
퀵정렬 : n개 -> a + b 분할 ->c+d+e+f
선택문제: n개 -> a + (b) 분할 ->(c)+d+(e+f) 분할한 것의 일부만 사용
이진탐색
> 정렬된 상태의 데이터에 대해 적용
분할 : 가운데 원소를 기준으로 왼쪽과 오른쪽 부분배열로 분할, 탐색키와 가운데 원소가 같으면 해당 원소의 배열 인덳를 반환/종료
정복 : 탐색 키 X가 가운데 원소보다 작으면 왼쪽 부분배열 대상으로 이진 탐색을 순환 호출, 크면 오른쪽 부분배열을 대상으로 이진탐색 순환 호출
결합 : 부분배열에 대한 탐색 결과가 직접 반환되므로 결합이 불필요
-순환형태-
BinarySearch(A[] , Left, Right, x)
{
if(Left > Right)return -1;//탐색 실패
Mid = (Left+Right/2);
if(x == A[Mid]) return Mid;
else if(x < Mid)Binary Search(A, Left, Mid-1, x) //왼쪽 부분배열
else BinarySearch(A, Mid+1, Right, x)//오른쪽 부분배열
}-반복형태- >> 효율이 좋음
BinarySearch(A[] ,n, x)
{
Left = 0; Right = n-1;
while (Left <=Right){
Mid ==(Left + Right)/2;
if(x==A[Mid]) return Mid;
else if (x<Mid) Right = Mid -1; //왼쪽 부분배열
else Left = Mid +1;//오른쪽 부분배열
}
return -1;
}n/2^k =1
k = logn ==> 데이터 8 개 면 3번 분할.
> 최대 비교횟수 = 최대 분할 횟수 +1 ==>4번 분할.
성능
T(n) : 입력 크기 n에 대한 탐색 가정에서의 모든 비교횟수의 합.
= 맨 바깥 수준에서의 비교횟수 + 순환 호출에서의 비교횟수.
-점화식-
T(n) = T(n/2) +O(1)(n>1), T(1) =1
T(n) = logn
>입력이 정렬된 리스트에 대해서만 적용가능
> 삽입/삭제 연산 시 데이터 정렬 상태 유지가 필요
- 평균 n/2개의 데이터 이동이 발생 -> 삽입/삭제가 빈번한 응용에는 부적합.
'Made by Miseong > 2019 알고리즘' 카테고리의 다른 글
| 2. 분할정복 - 퀵정렬 (0) | 2019.08.04 |
|---|---|
| 2019알고리즘 (0) | 2019.08.04 |