가장 가까운 점 쌍 (CLRS pg 1043) : 정렬 된 배열을 두 개의 정렬 된 배열로 분할하는 실행 시간

Question

O (nlgn) 시간에서 가장 가까운 점 쌍을 찾으면 정렬 된 목록을 두 개의 정렬 된 목록으로 분할하기위한 의사 코드 CLRS 3rd ed pg 1043)은 O (n) 시간에 실행된다고합니다.

그러나, 이것은 그 라인을 내가 믿기 어려운 찾을 일정 시간 4 개 실행을, 가정이 이진 트리로 저장 한 경우 (내가주는이) O (LGN 시간을 실행 가정 것 O (nlgn)의 총 실행 시간

Y는 정렬 된 배열이며, YL과 YR은 두 개의 새 하위 배열입니다 .PL은 임의 순서로 Y의 하위 집합이고 YL은 같은 하위 집합이지만

내가 이성으로 잘못 가고있는 곳은 무엇입니까?

Answer 1

간단히하기 위해 우리는 목록이 정수이고 문자열이나 정수가 아니라고 가정하고 있습니다.

루프

1. : 여기에 고려해야 할 두 가지 계산이 있습니다

   이 N은

2. 여기에 까다로운 부분이다 내가 있으리라 믿고있어하는 Y 시간의 길이 실행 - Y의 비교 [I] PL (참고 : 두 숫자의 비교는 워드 크기로 간주 할 경우 일정합니다.) 이제 랜덤 액세스 머신을 다루기 때문에 Y [i]에 액세스하는 것은 일정합니다. 그러나, 그것을 길이 PL의 배열 PL과 비교하기 위해, k는 k 시간이 걸릴 것이다. 이 k가 매우 작고 입력 배열 Y의 크기와 무관하다면 이상적으로는 일정 할 것입니다.

더 정밀하게 작성하려면 k 비교 (PL 길이)에 소요되는 시간을 고려해야하므로이 의사 코드의 총 시간은 O (Nk)가됩니다. 그러나 k가 무작위이고 N과 무관하다는 가정이 사실이라면 O (N)

Answer 2

나는이 책에서 어떻게 작동하는지 알지 못하지만 알고리즘의 모양을 생각하고있다. 같은, 당신은 다음과 같은 아이디어를 가지고 올 수 :

• Y[i], X[i], YL[i], XL[i], YR[i] 및 XR[i]는 i의 인덱스에 해당하는 정수 번째 점 (그래서 당신은 그냥 지구를 저장해야 인덱스를 지정하면 x 또는 y 좌표를 리턴하는 배열
• PL[i]은 i 번째 포인트가 왼쪽 부분에있는 경우 true이고, 그렇지 않은 경우 false입니다. 각 재귀 단계

, 당신은 PL[i] 사용 y 좌표 (O(n) 시간)을 계산할 수 있습니다. 그런 다음 책의 알고리즘을 사용하여 두 세트 "왼쪽"과 "오른쪽"의 점 집합을 분리하고 (이 액세스는 O(1)이므로 전체적으로 O(n)이됩니다) 행을 if Y[i] in PL으로 바꾸십시오.

이것은 복잡도가 O(n)이고 메모리가 O(n)입니다.

따라서 가장 가까운 쌍 문제는 T(n) = O(n log n)에서 그런 식으로 해결됩니다.