四叉树 O(N) 的最坏情况复杂度如何？
How can worst case complexity of quad tree O(N)?
当我阅读资料时，我了解到
最坏情况复杂度 of 四叉树是 O(N) 当 2D 矩阵只有一个 dimension.I 我无法理解原因为了这。
例如。当矩阵只有 1xm 时，我们将它继续分成两半，将达到 log(m) 中的单元 stops.So 复杂度应为 log(m)
谢谢
在最坏的情况下，您必须向下搜索到
树。考虑以下示例：除了级别 1 的 large quadrant/region 中的一个元素之外的所有元素，并且您需要访问至少一个元素的最低级别。我需要看你的幻灯片/书，但类似于 {{0,0},{0,1},{0,2},{0,3},{0,4},{0,5},{0,6},{0,63}} 的东西应该有用。
有多种构建四叉树的方法。如果您采用像素矩阵或任何单位并从中制作四叉树，那么它的高度确实是 log(n)。
但是，如果您使用它来存储一个接一个地添加的点（有点像 BST），那么如果您的所有点都根据一个组件排序，那么您将遇到最坏的情况.在这种情况下，树的高度将为 n.
这种情况的一个例子如下：
- 从一个空的四叉树开始
- 插入 (0,0)
- 插入 (1,1)
- 插入 (2,2)
- 插入 (3,3)
- ...
- 插入 (n-1,n-1)
每插入一个节点，它都会进入前一个插入节点的右上角，所以每个节点只有一个子节点。你最后得到的只是一个奇怪的长度为 n 的链表。
所以，这完全取决于你如何构建你的四叉树，并没有一个独特的方案来做到这一点。这就是为什么像 insert 或 search O(n).
这样的操作的最坏情况的复杂性
当我阅读资料时，我了解到 最坏情况复杂度 of 四叉树是 O(N) 当 2D 矩阵只有一个 dimension.I 我无法理解原因为了这。 例如。当矩阵只有 1xm 时，我们将它继续分成两半，将达到 log(m) 中的单元 stops.So 复杂度应为 log(m) 谢谢
在最坏的情况下，您必须向下搜索到
树。考虑以下示例：除了级别 1 的 large quadrant/region 中的一个元素之外的所有元素，并且您需要访问至少一个元素的最低级别。我需要看你的幻灯片/书，但类似于 {{0,0},{0,1},{0,2},{0,3},{0,4},{0,5},{0,6},{0,63}} 的东西应该有用。
有多种构建四叉树的方法。如果您采用像素矩阵或任何单位并从中制作四叉树，那么它的高度确实是 log(n)。
但是，如果您使用它来存储一个接一个地添加的点（有点像 BST），那么如果您的所有点都根据一个组件排序，那么您将遇到最坏的情况.在这种情况下，树的高度将为 n.
这种情况的一个例子如下：
- 从一个空的四叉树开始
- 插入 (0,0)
- 插入 (1,1)
- 插入 (2,2)
- 插入 (3,3)
- ...
- 插入 (n-1,n-1)
每插入一个节点，它都会进入前一个插入节点的右上角，所以每个节点只有一个子节点。你最后得到的只是一个奇怪的长度为 n 的链表。
所以，这完全取决于你如何构建你的四叉树，并没有一个独特的方案来做到这一点。这就是为什么像 insert 或 search O(n).
这样的操作的最坏情况的复杂性