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

Question

当我从资料中阅读时，我了解到 当二维矩阵只有一维时，四叉树的最坏情况复杂度为 O(N)。我无法理解其中的原因。 例如。当矩阵只有 1xm 时，我们将它继续分成两半，将在 log(m) 停止时到达单元格。所以复杂度应该是 log(m) 谢谢

Answer 1

有几种构建四叉树的方法。如果您采用像素矩阵或任何单位并从中生成四叉树，那么它的高度确实将为 log(n)。

但是，如果您使用它来存储一个接一个地添加的点(有点像 BST)，那么如果您的所有点都根据一个组件排序，那么您将遇到最坏的情况。在这种情况下，树的高度将为 n。

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

• 从一个空的四叉树开始
• 插入 (0,0)
• 插入 (1,1)
• 插入 (2,2)
• 插入 (3,3)
• ...
• 插入 (n-1,n-1)

每插入一个节点，它都会进入前一个插入节点的右上角，所以每个节点只有一个子节点。你最后得到的只是一个奇怪的长度为 n 的链表。

因此，这完全取决于您如何构建四叉树，并且没有一个独特的方案可以做到这一点。这就是为什么像 insert 或 search O(n) 这样的操作在最坏情况下的复杂性。