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））。作为一个家庭作业问题是不合理的，除非你希望谷歌而不是证明答案。这里有一个解决方案和证明：https://en.wikipedia.org/wiki/Closest_pair_of_points_problem –
@Brion这是奇怪的事情，我没有得到BandClosestPair的任何信息，距离只是一个简单的使用Sqrt的点dist方程。 – Diericx