목록최근접 점의 쌍 찾기 (1)

YJ_Scribbles

#A06_최근접 점의 쌍 분할 정복 알고리즘

★ 최근점 점의 쌍 찾기 - 차원 평면상의 n개의 점이 입력으로 주어질 때, 거리가 가장 가까운 한 쌍의 점을 찾는 문제 ☆ 간단한 방법 - 모든 점에 대하여 각각의 두 점 사이의 거리를 계산하여 가장 가까운 점의 쌍을 찾기 - 5개의 점이 아래의 [그림]처럼 주어지면, 1-2, 1-3, 1-4, 1-5, 2-3, 2-4, 2-5, 3-4, 3-5, 4-5 사이의 거리를 각각 계산하여 그 중에 최소 거리를 가진 쌍이 최근접 점의 쌍이 됨. ㅇ 비교해야 할 쌍은 몇 개인가? - nC₂ = n(n-1)/2 - n=5이면, 5(5-1)/2 = 10 - n(n-1)/2 = O(n²) - 한 쌍의 거리 계산 : O(1) - 시간복잡도 : O(n²)xO(1) = O(n²) ☆시간복잡도가 O(n²)보다 효율적인 방법..
이론_전공/알고리즘 2020. 9. 26. 22:58
이전 Prev 1 Next 다음