java - Set 付きのループの場合、O(n) ですか?

Question

私はループのためにこれを持っています:

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

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

このメソッドは O(n) にありますか?

score 4 · Accepted Answer

HashSet を使用する場合は、はい。 HashSetがあり、for ループを使用してO(1)乗算します。O(n)したがって、構造全体はを持っていO(n)ます。

score -1 · Accepted Answer

HashSetほぼ線形の挿入パフォーマンスがあるため、はい: n そのような操作は O(n) になります。

代わりにこれを行うことに注意してください。これにより、すべてのコードが行うこととまったく同じ結果が得られます。

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

上記のように、セットも入力する必要があります。

2 に答える 2