For循環Set，它是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)，並且使用for循環將它與O(n)相乘。因此，整個構造具有O(n)。

Answer 2

HashSet具有接近線性的插入性能，所以是的：n這樣的操作將是O（n）。

注意，我會做這個代替，達到完全相同的結果，因爲所有的代碼做什麼：

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

您shoukd鍵入您的設置也如上。