shyou1119   1년 전

Minimum Distance between Two Points - GeeksforGeeks

위 사이트를 참고하여 풀이했습니다. 시간 복잡도가 O(nlogn)이라고 되어있는데, 구현된 코드가 O(nlog^2(n))이라고 생각되어 질문드립니다.

우선, x축을 기준으로 정렬한 정점들을 인덱스 mid기준으로 가릅니다. 좌측, 우측에서 각각 구한 최소 거리 중 더 작은 값을 minDist라고 정의합니다.

이후, 해당 subproblem에 속하는 정점들 중 x값이 [points[mid].x - minDist, points[mid].x + minDist]에 속하는 정점들만 추출하여 y축에 대해 정렬합니다. 해당 정점들에 대해 이중반복문을 돌며 거리를 계산하고, minDist를 업데이트 합니다. 이 때 y축 차이가 minDist보다 크게 나면 다음 정점 비교로 들어가고, minDist를 계산한 원리 덕분에 각 정점마다 최대 7번까지 비교하는 부분은 이해했습니다. 범위에 속하는 정점 개수를 k라고 하면 y축 정렬에 O(klogk), 거리 계산에 O(k)가 들어 subproblem마다 O(klogk)의 시간 복잡도가 든다고 생각했습니다.

총 시간 복잡도를 계산하기 위해 각 단계를 t라고 하면, k는 최악의 경우 n / 2^t (subproblem의 크기)까지 될 수 있다고 생각했습니다. 각 단계의 subproblem 개수는 2^t개 이므로 시간복잡도는 O(klogk) * 2^t = O(n/2^t * log(n/2^t)) * 2^t = O(n * log(n/2^t)) = O(n * (log n - t))가 됩니다. 총 시간복잡도를 계산하기 위해 t=0부터 logn까지 더하면, (편의상 logn을 정수라 하겠습니다) O(n * (log n * log n - log n * (log n + 1) / 2)) = O(n * log^2 (n))이 된다고 생각했습니다.

제가 틀리게 생각한 것인지, 구현을 다르게 해야 O(nlogn)이 되는 것인지 궁금합니다.


zenith82114   1년 전

이 코드는 각 재귀마다 y 정렬을 새로 하기 때문에 O(n lg^2 n)이 걸립니다. 맨 처음에 모든 점의 y 정렬을 1번만 해놓으면, 각 재귀마다 병합정렬의 merge를 거꾸로 하듯이 좌우 분할한 점들에 대한 y 정렬 결과를 O(n)만에 얻을 수 있습니다.

댓글을 작성하려면 로그인해야 합니다.