0
나는이 숙제 문제를 알아 내려고하고 있지만 나는 너무 혼란 스럽다. 이 알고리즘 ClosestPair 알고리즘의 시간 복잡성을 찾아야하지만 얼마나 많은 시간을 계산할지 계산할 수는 없습니다. 여기에 지금까지이 작업은 다음과 같습니다이 재귀 알고리즘의 시간 복잡도를 어떻게 알 수 있습니까?
1. ClosestPair(S, p, r)
2. if p == r
3. return ∞
4. if r - p == 1
5. return Distance(S[p], S[p+1])
6. else
7. m = floor ((p+r)/2) //m is the index of the median (the x-coordinate is the vertical dividing line)
8. d1 = ClosestPair(S, p, m)
9. d2 = ClosestPair(S, m+1, r)
10. d = min(d1, d2)
11. SPrime = points in S within distance d from S[m].x sorted by y.
12. dPrime = BandClosestPair(Sprime, d)
13. return min(dPrime, d)
여기까지
1. 0
2. 1
3. 1
4. 1
5. 1
6. 1
7. 1
8.
9.
10. 1 (It's not actually 1 but it will be a constant so it won't affect the algorithm's time complexity)
11.
12.
13. 1
어떤 도움이 좋지 않을까 내 시간 복잡도입니다! 나는 당신이 내게 숙제를 해주기를 바라지 않는다. :
일반적으로 재귀와 같은 개체/값 집합에 대해 반복되는 루프 또는 것을 찾습니다. 그러나 ClosestPair, min, BandCloestPair, Distance와 같은 메서드 호출도 모두 평가해야합니다. 따라서 이러한 메소드의 구현을 살펴 봐야합니다. – Brion
비행기의 기하학적 특성 (특히 BandClosestPair가 O (n) 임)에 따라 달라 지므로 복잡성을 계산하는 것은 매우 어렵습니다. 당신이 대답을 증명하기보다는 오히려 google을 기대하지 않는다면 그것은 숙제 문제로 비합리적입니다. 해결책과 증명은 다음과 같습니다 : https://en.wikipedia.org/wiki/Closest_pair_of_points_problem –
@Brion 그건 내가 BandClosestPair에 대한 정보를 얻지 못했던 이상한 일입니다. 거리는 Sqrt를 사용하는 단순한 포인트 방정식입니다. – Diericx