为什么TreeSet迭代O(n)而不是O(n*logn)？

Question

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

每次下一次调用都需要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)时间.

Answer 1

一次next操作的最坏情况时间是O(log n)因为这是树的高度.但是,平均而言,可以及时找到下一个元素O(1).这是因为整个遍历本质上使用每个n-1树边缘两次.