一道算法题。
输入:
- 数据点列表
X - 数据点的度量函数
dist(x,y)需要 O(1) 时间来计算并服从三角不等式
是否有一种算法可以返回数据点向量 Y 使得 Y[i] 是 X 中最接近的点X[i] 次二次时间？
显然这在 O(n^2) 中是可能的，因为您可以直接检查每个点。我想知道是否有可能利用三角不等式来改进这一点。我也会对具有可证明边界的近似算法感兴趣(即类似 Y[i] 的东西不超过 (1 + log(n)) 乘以与 X[i]< 的距离 作为最小值)。
最佳答案
没有这样的算法。考虑一个度量，其中除了一对点之外的所有点都在距离 1 处。如果不咨询其特定的距离 oracle 条目，就无法找到这对点，这在最坏的情况下需要 Omega(n^2) 查询。
Cover trees可用于解决精确邻居问题。时间限制取决于指标的所谓倍增维度。
关于algorithm - 是否可以找到次二次时间所有点的最近点？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/41904461/