Java中设置的时间复杂度 [英] Time complexity of set in Java

问题描述

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

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

a 是一个int数组。

a is an array of 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 方法。

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.

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

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

推荐答案

我相信它的O（n）因为你循环遍历数组，并且包含和 add 应该是常量时间，因为它是基于 hash 的集合。如果它不是基于散列的并且需要在整个集合上进行迭代来进行查找，则上限将是n ^ 2.

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.

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

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

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

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.

EDIT-- yep这个类提供基本的恒定时间性能操作（添加，删除，包含和大小），假设散列函数在桶中正确地分散元素。

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."

参见这里。

这篇关于Java中设置的时间复杂度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！