补充讲解

KD-tree 查询复杂度分析

参考课件 07.BSTA.B6.kd-tree.Complexity

按照课件给出的建树方法，搜索过程花费的时间是 \(O(\sqrt n)\) , 如果需要依次汇报查找到的 \(r\) 个点，还需要额外 \(O(r)\) 的时间。

这个 \(O(\sqrt n)\) 是通过一个叫做 \(Q(n) = 2 Q(n/4) + O(1), Q(1)=O(1)\) 的递推式, 由主定理得到的。

那么这个递推式是如何得到的?

在查询的任意一层，我们考虑查询的矩形区域与当前节点的矩形区域的关系。

同时，我们考虑当前节点的两个子节点、以及子节点的子节点的划分，将当前节点的区域划分为四块。

问题在于，待查询的矩形区域，和这四块区域，位置关系如何？最多有几次向下递归的需要？

如果四块区域的某一块完全落在待查询矩形区域外，或者完全落在待查询矩形区域外，都不必向下递归。

乍一看，最多会产生4次向下的递归，只需要的待查询区域落在当前节点矩形区域的中央，和四块子节点的区域都有公共部分即可。

那么，递推式应该是\(Q(n) = 4*Q(n/4) + O(1), Q(1)=O(1)\) 才对？

一个重要的观察是，kd-tree的结构决定，不可能向下每一层递归时，都产生4次递归。不信你可以尝试举举例子，举不出来吧。

但是，也很容易举出例子，在产生4次递归后，再向下一层递归时，仍然会产生3次递归。

这里需要我们切换一下计数的方式。注意到，需要向下递归，其实可以看作是查询区域的边界和kd-tree矩形区域划分的边界相交形成的。

我们可以说，将kd-tree的矩形区域划分到第L层，看看查询区域的边界和kd-tree当前的矩形区域划分有多少交点，就意味着查询过程中，在第L层需要向下递归多少次。注意到，每一个需要向下递归的子节点，其对应的矩形区域，都和当前的查询区域边界有两个交点，而每个交点又是由两个需要向下递归的子节点共用的。可以想象，第L层，需要向下递归的所有节点应该形成一个环形（围绕查询区域的边界）。

因此我们可以说，第L层向下递归的节点总数 = 第L层的kd-tree小矩形边界和查询区域边界的交点总数。

注意到，查询区域的矩形边界是由4根线段组成的。因此，实际上我们只需要考虑，一根线段，会在每一层的待查询节点共形成多少个交点。

最终结果需要乘4, 不影响渐进复杂度结果。

到这一步，我们才能比较简单地得到 \(Q(n) = 2 Q(n/4) + O(1), Q(1)=O(1)\) 的递推式。

\(Q(n)\) 的含义是，在包含n个点的一个kd-tree节点中，一根线段，最多能贡献多少个交点。

它的计算方法是，这个节点的本层贡献了 \(O(1)\) 个交点。而向下考虑两层，最多有两个规模为 n/4 的节点内部可能和这根线段继续相交、贡献交点。

而关于为什么“最多有两个”的证明，可以参考课件的插图。也可自行思考如何给出更严谨的证明。