我想知道是否有一种算法可以在优于 O(n) 的时间内计算最近的位置(由纬度/经度表示)。
我知道我可以使用 Haversine 公式来获取从引用点到每个位置的距离并按 ASC 排序，但这对于大型数据集来说效率很低。
MySQL DISTANCE() 函数如何执行？我猜 O(n)？
最佳答案
如果您使用 kd-tree要存储您的点，您可以在 O(log n) 时间(预期)或 O(sqrt(n)) 最坏情况下执行此操作。
关于algorithm - 可以在优于 O(n) 的时间内通过纬度/经度计算最近的位置吗？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/1197863/