java - 带Set的for循环，是O(n)吗？

Question

我有这个 for 循环：

public void method(int[] arr) {
    Set set = new HashSet();

    for(int i = 0; i < arr.length; i++){
        set.add(arr[i]);
    }
}

这个方法在 O(n) 中吗？

Answer 1

如果你使用 HashSet，是的。 HashSet有O(1)并且你O(n)通过使用一个for循环来乘以它。因此，整个构造具有O(n).

Answer 2

HashSet具有近线性的插入性能，所以是的：n 这样的操作将是 O(n)。

请注意，我会改为这样做，这与您的所有代码所做的结果完全相同：

Set<Integer> set = new HashSet<Integer>(Arrays.asList(arr));

如上所述，您也应该键入您的 Set。