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を使用しているので、私はわからないんだけど、これは、同様のメソッドが含まれています。またaddメソッドをsetと呼びます。

上記のコード全体の時間の複雑さを確認して説明できますか？また、どれくらいのスペースが必要ですか？

Answer 1

そのハッシュベースのセットので、あなたの配列をループし、containsとaddは一定の時間でなければなりませんので、私は（n）はそのOを信じています。ハッシュベースではなく、ルックアップを行うためにセット全体にわたって反復が必要な場合、上限はn^2になります。

整数は不変なので、空間の複雑さは2nになります。これは、定数が問題ではないため、nだけ単純化すると考えられます。あなたは、配列やセット内のオブジェクトを持っていた場合

、あなたは2nの参照とn個のオブジェクトを持っているでしょう、あなたはまだ、リニア（回一定の）スペースの制約である3N、です。

EDIT_yep "このクラスは、ハッシュ関数がバケット間で要素を適切に分散すると仮定して、基本的な操作（追加、削除、包含、サイズ）に一定の時間パフォーマンスを提供します。

hereを参照してください。