我有一个 100 维空间中有 500,000 个点的数据库，我想找到最接近的 2 个点。我该怎么做？
更新：空间是欧几里得的，抱歉。并感谢所有的答案。顺便说一句，这不是家庭作业。
里面有一章算法简介 http://en.wikipedia.org/wiki/Introduction_to_Algorithms致力于在 O(n*logn) 时间内找到二维空间中两个最近的点。你可以在以下网站查看。事实上，我建议每个人都这样做，因为他们应用分而治之技术来解决这个问题的方式非常简单、优雅且令人印象深刻。
虽然它不能直接扩展到你的问题（作为常数7将被替换为2^101 - 1），对于大多数数据集来说应该没问题。所以，如果你有相当随机的输入，它会给你O(n*logn*m)复杂度在哪里n是点数并且m是维数。
edit
这都是假设你有欧几里得空间。即向量的长度v is sqrt(v0^2 + v1^2 + v2^2 + ...)。但是，如果您可以选择指标，则可能还有其他选项来优化算法。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
