java - 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 并且它也包含方法。它还调用了 set 的 add 方法。

任何人都可以确认并解释上面整个代码的时间复杂度是多少？另外，需要多少空间？

Answer 1

我相信它的 O(n) 因为你遍历数组，contains 和 add 应该是常数时间，因为它是一个 hash基于集。如果它不是基于散列的并且需要对整个集合进行迭代以进行查找，则上限将为 n^2。

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

如果您在数组和集合中有对象，那么您将有 2n 个引用和 n 个对象，所以您有 3n 个，这仍然是线性(乘以常数)空间限制。

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

参见 here .