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, Distance - просто простое уравнение точечного разряда, использующее Sqrt. – Diericx