위 사이트를 참고하여 풀이했습니다. 시간 복잡도가 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)이 되는 것인지 궁금합니다.
shyou1119 1년 전 2
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)이 되는 것인지 궁금합니다.