complexity-theory - 随机填充的四叉树中的平均搜索复杂度

我有一个四叉树，里面有 N 个随机 2D 点 (x,y)。

我要估计这两种情况下的平均搜索复杂度是多少

1) 范围搜索（从位置 x,y 的距离 R 内）

2) 单个最近点 (x,y)

到目前为止，我的推理如下 - 如果我们与二叉树的平均复杂度进行类比 - https://en.wikipedia.org/wiki/Binary_search_tree

哪个是

$log_{2}N$

对于单次搜索，QuadTree 的平均复杂度应该类似于（因为有 4 个孩子）：

$O(log_{4}N) + 4O(k)$

k 应该取决于是否在范围内必须检查的平均点数（但我不确定如何估计它，即使对于单个点，仍然必须在圆内进行范围搜索）。在 R 较大的最坏情况下，我们必须检查所有点，复杂度会恶化到 O(N)。

谢谢。

标签： complexity-theoryquadtree