二维平面中任意点（自身除外）的最近邻点
Closest neighbor to any point (other than itself) in a 2D plane
给定一个二维平面和N个点(n1=(x1,y1), n2=(x2,y2)..., nN=(xN,yN))，什么是快速的(O(n)或更好）算法，它将找到任何点的最近邻居（例如，n1 最近邻居是 n3，n2 最近邻居是 n4）。我正在考虑将它存储在字典中，其中键是点，值是邻居。
SO上好像有很多类似的问题，但是我找不到Python中的任何代码或者不是其他语言的答案。
对于给定的点P，简单解：
- 计算 P 与所有其他点的距离，这是用 O(n) 时间复杂度完成的。
- 将它们保存为元组列表（或类似的数据结构），（点，距P的距离）的元组。
- 在 O(n) 的时间复杂度内，遍历列表可以得到前 K 个最接近的点。
第二个解决方案在 space 复杂度 (O(n^2)) 和随时间推移的维护方面会花费更多，但会缩短查找 K 个最近邻居的时间：
- 根据点的距离保存从每个点到点的有序列表（或类似数据结构）的字典 - 构建这个table一次是 O(n^ 2 * 日志(n)).
- 找到 K 个最近点的时间复杂度为 O(k) - 字典访问 + 从有序列表中复制 k 个元素。
- 时间复杂度的开销是添加一个新点或删除一个旧点，以保持此数据结构有效 - O(n*log(n)) 在两者中。
您选择的解决方案应针对您要优化的内容
一个简单的解决方案可以产生比平均 O(n) 更好的结果是使用 k-d 树 来存储点。构建树的最坏情况复杂度为 O(nlogn)。之后搜索平均为 O(logn)，最坏情况为 O(n)（通常用于远离所有其他数据的点）。
此外，您可能对 LSH 或局部敏感哈希感兴趣，虽然它是一种近似方法，这意味着您不会总是得到正确的答案，对于高维数据，它提供了重要的加速，复杂性与参数密切相关已选择。
给定一个二维平面和N个点(n1=(x1,y1), n2=(x2,y2)..., nN=(xN,yN))，什么是快速的(O(n)或更好）算法，它将找到任何点的最近邻居（例如，n1 最近邻居是 n3，n2 最近邻居是 n4）。我正在考虑将它存储在字典中，其中键是点，值是邻居。
SO上好像有很多类似的问题，但是我找不到Python中的任何代码或者不是其他语言的答案。
对于给定的点P，简单解：
- 计算 P 与所有其他点的距离，这是用 O(n) 时间复杂度完成的。
- 将它们保存为元组列表（或类似的数据结构），（点，距P的距离）的元组。
- 在 O(n) 的时间复杂度内，遍历列表可以得到前 K 个最接近的点。
第二个解决方案在 space 复杂度 (O(n^2)) 和随时间推移的维护方面会花费更多，但会缩短查找 K 个最近邻居的时间：
- 根据点的距离保存从每个点到点的有序列表（或类似数据结构）的字典 - 构建这个table一次是 O(n^ 2 * 日志(n)).
- 找到 K 个最近点的时间复杂度为 O(k) - 字典访问 + 从有序列表中复制 k 个元素。
- 时间复杂度的开销是添加一个新点或删除一个旧点，以保持此数据结构有效 - O(n*log(n)) 在两者中。
您选择的解决方案应针对您要优化的内容
一个简单的解决方案可以产生比平均 O(n) 更好的结果是使用 k-d 树 来存储点。构建树的最坏情况复杂度为 O(nlogn)。之后搜索平均为 O(logn)，最坏情况为 O(n)（通常用于远离所有其他数据的点）。
此外，您可能对 LSH 或局部敏感哈希感兴趣，虽然它是一种近似方法，这意味着您不会总是得到正确的答案，对于高维数据，它提供了重要的加速，复杂性与参数密切相关已选择。