为什么TreeSet迭代的时间复杂度是O(n)，而不是O(n*logn)？

Question

我读到了一个关于TreeSet时间复杂度的先前问题，答案是它需要O(n)的时间。然而，我不明白为什么迭代的时间复杂度是O(n)，而不是O(n*nlogn)。

每次next调用需要O(logn)的时间

因此，如果我像这样遍历TreeSet：

while (iterator.hasNext()){ //Runs N times
   System.out.println(iterator.next() + " "); //each next is O(logn)
}

我希望它是O(n*logn)而不是O(n)，因为while循环有N次迭代，每次iterator.next()调用需要花费O(logn)的时间。

- Eric

---

为什么 iterator.next() 的时间复杂度是 O(log n)。它只需要访问下一个节点，这应该是 O(1)，不是吗？ - Jose Luis

@JoseLuis不准确，基于查看源代码。 - Louis Wasserman

@louis-wasserman 你是对的，非常抱歉。我认为iterator()可以返回一个排序后的节点列表，然后转到下一个节点就很容易了。 - Jose Luis

Answer 1

一个next操作的最坏时间复杂度为O(log n)，因为这是树的高度。然而，在平均情况下，下一个元素可以在O(1)时间内找到。这是因为整个遍历实际上使用了每个n-1个树边两次。

- David Eisenstat

---

Iterator.next 的代码似乎最终会出现在 TreeMap.Entry.successor() 中，链接在这里：http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/6-b14/java/util/TreeMap.java#TreeMap.successor%28java.util.TreeMap.Entry%29 是的，大多数情况下下一个条目只是 p.left != null。 但是，Big-O不应该是最坏情况，而不是平均情况吗？ - markspace

@markspace Big-O 描述你想要的任何行为，因为它不是关于复杂度本身，而是关于函数增长。你可以描述平均、最坏、分摊、期望成本，以及高概率等。在这种情况下，所有操作的最坏和最好情况都是 Theta(n)。查找单个后继可能需要花费 log n 时间，但迭代所有 n 个元素的成本最多为 2n。 - G. Bach

@markspace 没有详细说明的大O界限是指最坏情况下的运行时间，但大O符号只是关于函数的数学陈述。 - David Eisenstat

@markspace 是的，每个 iterator.next() 调用的最坏时间复杂度为 O(log n)。但同时，遍历整个 TreeSet 的最坏时间复杂度为 O(n)。（并且在上面给出的答案中，如果你遍历整个 TreeSet，那么在最坏情况下，iterator.next() 的平均时间复杂度将为 O(1)。） - Louis Wasserman

Answer 2

您可以像这样为树实现迭代：

void print(Node n) {
   if (n.left != null) print(n.left);
   System.out.println(n.value);
   if (n.right != null) print(n.right);
}

函数print将会被每个节点恰好调用一次，因此总迭代时间为O(N)。您可以迭代地实现完全相同的算法（无需递归）。如果您足够小心，可以使用类来保持迭代状态，并在调用.next()时推进。虽然在println之间的函数调用数量不均匀，但是总体上看，您会发现它们恰好有N个。

- Sorin