3

我已经搜索过这些信息。发现这个：

https://groups.google.com/forum/#!topic/uw.cs.cs240/MGfrsvKAiMA

和这个：

四叉树 O(N) 的最坏情况复杂度如何？

，但我不相信它回答了我的问题。第一个，也许，但我不明白解释。说到点子上了。

我在离散空间（实体的二维方表）上有一个四叉树。它是一个区域树，如英文维基百科页面 ( https://en.wikipedia.org/wiki/Quadtree#Types ) 中所述。每个区域只能拥有一个实体。每个实体都有其离散坐标。

queryRange()我已经实现了一种方法来查找特定（离散）AABB 中的所有实体，其工作方式与上述 Wiki 页面中的功能完全相同。

我的问题是：这个queryRange()函数的时间复杂度是多少？

我试过自己弄清楚，但它似乎取决于许多不同的因素，例如：树的深度、树中元素的数量、给定 AABB 的大小。我认为它的核心与 queryRange() 递归访问的子树的数量有关。

我也将感谢任何可靠的消息来源。我正在写一篇硕士论文，我需要引用。不过，我似乎真的无法在这个主题上搜索到任何好的内容。

4

1 回答 1

3

查询的时间复杂度取决于很多方面：

  1. 数据分布
  2. 插入顺序（除非您重新平衡树）
  3. 无论您存储点还是矩形（据我所知，点更常见）
  4. 您正在执行的查询类型

我不是复杂度计算方面的专家，因此可能有某种方法可以计算平均复杂度，但对于给定的实际场景可能没有用。

最大复杂度要容易一些。可以说n是条目数，h是树的高度。

一个大查询显然会返回所有元素，所以复杂度是 O(n)。一个非常窄的查询必须从根遍历到恰好一个叶子，因此 O(h)。这给出了组合的 O(n+h)。

有一些边界情况：例如，如果数据的形状使得所有点都在一条线上 (0,1),(0,2),(0,3),(0,4),...并且它们按顺序插入，然后树可能会退化为一个列表，使得 h=n，除非您执行一些重新平衡。

如果您对四叉树变体感兴趣，您可能需要查看最近的PH-Tree。PDF包含一些复杂性计算。PH-Tree 是基于比特级特里树分解的区域四叉树（分解成象限）。因此，最大深度等于值中的位数，通常为 32 或 64。该结构与插入顺序无关，因此不需要重新平衡（也不需要重新平衡，因为深度是有限的）。可以在此处找到一些技术更新。（免责声明：这是基于我在大学时自己的研究）。

于 2016-09-14T21:50:14.123 回答