Java中设置的时间复杂度

Question

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

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]);
}

我认为它是O(n),但我不确定,因为它正在使用Set,这也包含方法.它也在调用add方法set.

任何人都可以确认并解释上述代码的时间复杂度是多少？还需要多少空间？

Answer 1

我相信它的O(n)因为你循环遍历数组,contains并且add应该是恒定时间因为它是基于散列的集合.如果它不是基于散列的并且需要在整个集合上进行迭代以进行查找,则上限将是n ^ 2.

整数是不可变的,因此空间复杂度为2n,我认为这简化为n,因为常数无关紧要.

如果你有数组中的对象并设置,那么你将有2n个引用和n个对象,所以你是3n,它仍然是线性的(乘以常数)空间约束.

编辑 - 是的"这个类为基本操作(添加,删除,包含和大小)提供恒定的时间性能,假设散列函数在桶中正确地分散元素."

看到这里.