问如何使用kd-树计算最近邻搜索的平均时间复杂度？

EN

本文的计算尽可能简单，以便进行严格的分析。

(注:这是成为一名真正的计算机科学家和软件工程师的代价。你必须努力学习数学。懂得数学是区分那些认为自己能写出可靠程序的人和真正能写程序的人之间的区别。乔恩·本特利( Jon )，发明了kd-tree的人，在他上高中的时候就这样做了。以这个为灵感。)

如果你想要一个不严格的粗略的直觉想法，这里有一个。

假设我们在2d工作。二维树表示的几何区域的大小是关键。

在平均情况下，一个点将域划分为2个大小大致相等的矩形.3点分为4.7点分为8部分。等。通常情况下，N点会导致N-1的大小大致相等的矩形.

不难看出，如果域为1x1，则这些部分的边长平均为O(sqrt(1/N))。

搜索最近的邻居时，将树下降到包含搜索点的矩形。完成此操作后，您已经使用了O(log )方法在R= O(sqrt(1/ N) )中找到一个正确的点。这只是你发现的叶子中的一个点。

但这个矩形并不是唯一必须搜索的矩形。您仍然必须查看所有其他包含一个点不超过距离R的搜索点，细化R每次你找到一个更近的点。

幸运的是，R上的O(sqrt(1/N))限制为其他矩形的平均数量提供了一个紧界。在平均情况下，它大约是8，因为每个等大小的矩形没有超过8个邻居。

所以搜索的总工作量是O(8 log n) = O(log n)。

我再说一遍，这不是一个严格的分析，但它应该给您一个感觉，为什么算法是O(log )在一般情况下。