3.4 최근접 점의 쌍(Closest Pair of Points) 찾기
:2차원 평면 상의 n개의 점이 주어질 때, 거리가 가장 가까운 한 쌍의 점을 찾는 문제
✔️ O(n^2) 보다 효율적인 분할 정복 이용
- 중간 영역에 있는 점들을 찾는 방법
1) d = min{왼쪽 부분의 최근접 점의 쌍 사이 거리, 오른쪽 부분의 최근접 점의 쌍 사이 거리}
2) 배열에는 점들이 x좌표의 오름차순으로 정렬되어 있고, y좌표는 생략
3) 중간 영역에 속한 점 = {왼쪽 부분 문제의 가장 오른쪽 점(왼쪽 중간점)의 x좌표에서 d를 뺀 값과 오른쪽 부분 문제의 가장 왼쪽 점(오른쪽 중간점)의 x좌표에 d를 더한 값 사이의 x좌표 값을 가진 점들}
✔️ 알고리즘
//-
시간 복잡도
S에 n개의 점이 있으면 전처리 과정으로서 S의 점을 x좌표로 정렬: O(nlogn)
k층까지 분할된후, 층별로 line5~6이 수행되는 취합 과정
1) 각 층의 수행 시간은 O(nlogn)
2) 층 수인 log n 을 곱하면 O(nlog^2n)
//(log^2n) = (log n)(log n) -
O(nlog^2n) => O(nlogn) ?
3.5 분할 정복 적용에 있어 주의할 점
1) 분할 정복이 부적절한 경우
- 입력이 분할될 때마다 분할된 부분 문제의 입력 크기의 합이 분할되기 전의 입력 크기보다 커지는 경우
2) n번째의 피보나치 수 구하기
