四叉树O（N）的最坏情况如何复杂？ [英] How can worst case complexity of quad tree O(N)?

问题描述

从源头上我读到，当2D矩阵只有一个维度时，我发现
四分之一树的最差情况复杂度是O（N）。我不明白这个原因。
例如当矩阵只有1mm时，我们会把它分成两半，并以log（m）的方式到达单元格。复杂度应该是log（m）
THANKS

解决方案

有几种构建四叉树的方法。如果你采取一个像素矩阵，或任何单位，并做出一个四叉树，那么它的高度将是log（n）。

但是，如果你使用它存储一个接一个地添加的点（类似于BST），那么如果所有的点都根据一个组件进行排序，那么你将会遇到最坏的情况。在这种情况下，树的高度为n。

这种情况的一个例子如下：

• 从空的四叉树开始


• 插入（0,0）


• 插入（1,1）


• 插入（2,2）


• 插入（3,3）


• ...


• 插入（n-1，n-1）

每次插入节点时，进入先前插入的节点的右上角，因此每个节点只有一个孩子。你最后得到的只是长度为n的奇怪的链表。

所以，这一切都取决于你如何构建四叉树，而没有一个独特的方案要做到这一点。这就是为什么操作的最糟糕的复杂性，如 insert 或搜索 O（n）。

As I read from sources,I learnt that worst case complexity of Quad tree is O(N) when the 2D matrix has only one dimension.I am not able to understand the reason for this. For eg. When matrix is just 1xm,we'll keep dividing it into two halves and will reach unit cell in log(m) stops.So complexity should be log(m) THANKS

解决方案

There are several ways of building a quad tree. If you take a matrix of pixels, or whatever units and make a quadtree out of it, then indeed it's height will be log(n).

However, if you use it to store points (kind of like a BST) that you add one after the other, then you'll hit the worst-case scenario if all of your points are sorted according to one components. In this case, height of the tree will be n.

An example of such a case is the following:

• Start with an empty quad tree
• Insert (0,0)
• Insert (1,1)
• Insert (2,2)
• Insert (3,3)
• ...
• Insert (n-1,n-1)

Each time you insert a node, it goes into the upper right corner of the previously inserted node, so each node has exactly one child. What you get at the end is just a weird linked list of length n.

So, it all depends of how you build your quadtree, and there is not a unique scheme to do that. That's why the worst-case complexity for operations like insert or search O(n).

这篇关于四叉树O（N）的最坏情况如何复杂？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！