在Java中设置的时间复杂度

Can someone tell me the time complexity of the below code?

有人能告诉我以下代码的时间复杂度吗?

a is an array of int.

a是int的数组。

Set<Integer> set = new HashSet<Integer>();
for (int i = 0; i < a.length; i++) {
    if (set.contains(arr[i])) {
        System.out.println("Hello");
    }
    set.add(arr[i]);
}

I think that it is O(n), but I'm not sure since it is using Set and this contains methods as well. It is also calling the add method of set.

我认为它是O(n)，但我不确定，因为它使用的是Set，它也包含方法。它还调用set的add方法。

Can anyone confirm and explain what the time complexity of the entire above code is? Also, how much space would it take?

是否有人能确认并解释以上代码的时间复杂度?而且，它需要多少空间?

1 个解决方案

#1

i believe its O(n) because you loop over the array, and contains and add should be constant time because its a hash based set. If it were not hash based and required iteration over the entire set to do lookups, the upper bound would be n^2.

我相信其O(n)因为你循环数组,包含和添加应该持续的时间,因为它基于散列的集合。如果不是基于散列和查找所需的迭代整个组,上界将n ^ 2。

Integers are immutable, so the space complexity would be 2n, which I believe simplifies to just n, since constants don't matter.

整数是不可变的，所以空间复杂度是2n，我认为简化为n，因为常数不重要。

If you had objects in the array and set, then you would have 2n references and n objects, so you are at 3n, which is still linear (times a constant) space constraints.

如果数组和集合中有对象，那么就有2n个引用和n个对象，所以是3n，它仍然是线性的(乘以常数)空间约束。

EDIT-- yep "This class offers constant time performance for the basic operations (add, remove, contains and size), assuming the hash function disperses the elements properly among the buckets."

编辑——是的，“这个类为基本操作(添加、删除、包含和大小)提供了恒定的时间性能，假设散列函数将元素适当地分散到存储桶中。”

see here.

在这里看到的。

#1