从HashSet获取stream filter的时间复杂度是多少？

Question

Set<Integer> set = new HashSet<>();
set.add(1);
set.add(2);
...

下面操作的时间复杂度是多少？ O(n) 或 O(1)？

set.stream().filter(e -> e == 1).findFirst();

Answer 1

换个角度看会更明白，你的解决方法是这样的:

for(Integer i : set){
    if(i == 1){
        break;
    }
}

所以是O(n)因为它遍历了所有的集合，一个一个的检查，如果条件正确returnelse的值继续直到 n elsement

Answer 2

它是 O(n) - 在您创建一个 Stream 实例后，您不再在 HashSet 上操作，而是在 Stream 遍历源 Set 的所有元素。

这是一个惰性线性序列，其中所有元素都被一个一个地访问 - 因此 O(n)

What is the time complexity of stream filter obtained from HashSet?