假设我们有两组点,比如平面中的A和B(都是O(n)
)我们能在O(n)
时间内找到A&B中最远的一对点吗?
最佳答案
不,您不能计算O(n)
中每个点的最远点你能得到的最好的是O(n log n)
和2-d tree你可以用一种类似于寻找最近点的技术来实现这一点。
阅读一篇更详细的answer here文章,其中我展示了一些解决类似问题的其他方法。
关于algorithm - 计算每个点的最远点,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/36787024/