자바 : 거리 측정 알고리즘 설계

Question

내가 자바에서 다음과 같은 문제가 (이 꽤 많이에서 다른 언어를 할 수 있지만) 해결하려고 노력하고 있어요 :

I는 정수 값의 두 배열, xs 및 ys을 부여하고를 x 축의 dataPoints를 나타냅니다. 둘 다 0보다 크지 만 길이가 동일하지 않을 수 있으며, 정렬 할 필요가 없습니다. 제가 계산하고자하는 것은 두 개의 데이터 세트 사이의 최소 거리를 측정하는 것입니다. 제가 의미하는 바는 각각에 대해 xys 집합에서 가장 가까운 y을 찾고 거리를 계산합니다 (예 : (x-y)^2). 예를 들어 :

xs = [1,5] 
ys = [10,4,2] 

가 반환해야합니다 (1-2)^2 + (5-4)^2 + (5-10)^2

거리 측정, 그것은 내가 알고리즘 중요하지 않습니다 관심이. 둘 다 정렬 배열에 대해 어떻게 든 더 나은 무언가를 달성하기 위해 두 배열의 사전 인덱스를 생각했다 (각 elem에 대한 x, 스캔 ys 모든 elems 스캔) O(len1 * len2)입니다.

이것은 숙제 문제가 아닌 내 자신의 문제입니다. 귀하의 모든 힌트는 크게 감사하겠습니다.

Answer 1

HighPerformanceMark (질문에 대한 첫 번째 의견)가 맞다고 생각하고 실제로 더 큰 배열을 가져 와서 각 요소에 대해 더 작은 배열 중 가장 가까운 배열을 찾아 그 거리에 대해 f (dist)를 합산합니다. 정렬에 대한 O(max(len1,len2)*log(max(len1,len2)))입니다

Sort both arrays 
indexSmall=0 

// sum up 
for all elements e in bigArray { 
    // increase index as long as we get "closer" 
    while (dist(e,smallArray(indexSmall)) > dist(e,smallArray(indexSmall+1)) { 
    indexSmall++ 
    } 
    sum += f(dist(e,smallArray(indexSmall))); 
} 

:

나는 당신의 접근 방식을 제안합니다. 나머지는 더 큰 배열 길이에 선형입니다. 이제 dist(x,y)은 abs(x-y) 및 f(d)=d^2 또는 원하는대로 표시됩니다.

Answer 2

나에게 좋은 아이디어가 떠 올랐습니다. O (n logn) 시간에 목록을 정렬 할 수 있습니다. 그런 다음 다른 목록에서 슬라이딩 인덱스를 사용하여 긴 목록에서 단일 반복을 수행하여 "쌍"을 찾을 수 있습니다. 긴 목록을 진행할 때 다른 목록으로 되돌릴 필요가 없습니다. 이제 전체 알고리즘은 O (n log n + n) = O (n log n)입니다.

Answer 3

귀하의 접근 방식은 상당히 좋으며 O(n1*log(n1)+n2*log(n2)) 시간 복잡성이 있습니다. 배열은 길이가 다른 경우

, 다른 접근 방식이다 :

1. 종류의 짧은 배열;
2. 이진 검색을 사용하여 정렬 된 짧은 배열에서 가장 가까운 항목을 찾으려면 긴 배열을 처음부터 끝까지 탐색합니다.

이 n1가 짧은 배열의 길이 O((n1+n2)*log(n1)) 시간 복잡도를 갖는다.