我们知道kd树最近邻搜索的复杂度是O(logn)。但是如何计算它呢？主要问题在于回溯的平均时间复杂度。我尝试阅读了论文“一种在对数期望时间内寻找最佳匹配的算法”，但对我来说太过复杂了。有没有人知道一种简单的计算方法？
如何使用kd-tree计算最近邻搜索的平均时间复杂度？
4
- PyChen
2
1这个问题可能更适合在 [cs.se] 上提问。 - Bernhard Barker
如果你是真正的程序员而不是骗子，这是一个合理的问题。 - Gene
1个回答
7
这篇论文的计算尽可能简单，用于严谨分析。
（注：这是成为真正的计算机科学家和软件工程师所必须付出的代价。您必须努力学习数学。掌握数学是区分那些认为自己可以编写稳健程序和那些实际上可以的人之间的关键因素。发明kd树的Jon Bentley在高中时就做到了这一点。把它当作启示吧。）
如果您想要一个粗略的直观想法，而不是严格的分析，请看这里。
假设我们正在处理二维数据。2d树表示的几何区域的大小是关键。在平均情况下，一个点将域划分为大致相等大小的矩形。3个点将其分为4个部分。7个点将其分为8个部分。以此类推。一般来说，N个点导致N-1个大致相等大小的矩形。
很容易看出，如果域是1x1，则这些部分的边长平均为O(sqrt(1/N))。
当您搜索最近的邻居时，您会下降到包含搜索点的矩形中。完成这一步后，您已经花费O(log N)的代价找到了一个距离正确的点不到R = O(sqrt(1/N))的点。这只是您发现的叶子中包含的一个点。
但是，这个矩形并不是唯一必须搜索的矩形。您仍然必须查看所有包含距离搜索点不超过R的点的其他矩形，并在每次找到更近的点时进行精细调整。
幸运的是，对R的O(sqrt(1/N))限制提供了其可以的平均数量的其他矩形的紧密界限。在平均情况下，它大约为8，因为每个大小相等的矩形都不超过8个邻居。
因此，搜索的总代价为O(8 log n) = O(log n)。
再次强调，这不是严格的分析，但应该让您了解算法在平均情况下为O(log N)的原因。
（注：这是成为真正的计算机科学家和软件工程师所必须付出的代价。您必须努力学习数学。掌握数学是区分那些认为自己可以编写稳健程序和那些实际上可以的人之间的关键因素。发明kd树的Jon Bentley在高中时就做到了这一点。把它当作启示吧。）
如果您想要一个粗略的直观想法，而不是严格的分析，请看这里。
假设我们正在处理二维数据。2d树表示的几何区域的大小是关键。在平均情况下，一个点将域划分为大致相等大小的矩形。3个点将其分为4个部分。7个点将其分为8个部分。以此类推。一般来说，N个点导致N-1个大致相等大小的矩形。
很容易看出，如果域是1x1，则这些部分的边长平均为O(sqrt(1/N))。
当您搜索最近的邻居时，您会下降到包含搜索点的矩形中。完成这一步后，您已经花费O(log N)的代价找到了一个距离正确的点不到R = O(sqrt(1/N))的点。这只是您发现的叶子中包含的一个点。
但是，这个矩形并不是唯一必须搜索的矩形。您仍然必须查看所有包含距离搜索点不超过R的点的其他矩形，并在每次找到更近的点时进行精细调整。
幸运的是，对R的O(sqrt(1/N))限制提供了其可以的平均数量的其他矩形的紧密界限。在平均情况下，它大约为8，因为每个大小相等的矩形都不超过8个邻居。
因此，搜索的总代价为O(8 log n) = O(log n)。
再次强调，这不是严格的分析，但应该让您了解算法在平均情况下为O(log N)的原因。
- Gene
3
非常感谢您不仅回答了我的问题，还给了我建议。它们都是我想要的。谢谢 :) - PyChen
@Gene，我有些难以完全理解原始证明。既然您似乎知道并理解原始证明，那么我可以引起您对一个后续问题的关注吗？我在CS.SE上创建了一个新问题，因为评论似乎不合适。 - user1494080
@user1494080 你删掉了你的问题吗？ - Jill-Jênn Vie
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接