Java中Iterator()的时间复杂度

Question

我是Java的新手。关于java iterator()的时间复杂度，我有一个问题。

Set<Integer> set = new HashSet<>();

Iterator<Integer> iter = set.iterator(); ==> (2)

我想知道步骤2的时间复杂度是什么？它是常数时间O(1)还是取决于集合的大小？谢谢。

- Aaron

Answer 1

调用iterator()是常数时间。这是一个方法调用，它在你所调用的集合上返回一个Iterator实例。使用while (hasNext())迭代器实际遍历集合将花费O(n)的时间。

- kjsebastian

Answer 2

当您调用iterator（）方法时，您并没有在任何地方循环。此方法只是返回元素上的迭代器，并且该时间是恒定的，因此您不会为此计算时间复杂度。

您在访问一组元素时计算时间复杂度。例如，当您像这样访问元素时：

while(iterator.hasNext()) {
   Object element = iterator.next();
}

这是您可以计算时间复杂度的地方，在这种情况下，它将为O(n)。

- Raman Sahasi