Java'da ayarlanan zaman karmaşıklığı

Question

Birisi bana aşağıdaki kodun zaman karmaşıklığını söyleyebilir mi?

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]); 
} 

Ben O (n) olduğunu düşünüyorum, ama bu Set kullanıyor beri emin değilim ve bu yanı yöntemlerini içerir. Ayrıca set'un add yöntemini çağırıyor.

Yukarıdaki kodun zaman karmaşıklığının ne olduğunu herkes onaylayabilir ve açıklayabilir mi? Ayrıca, ne kadar yer alır?

Answer 1

i dizi üzerindeki O (n) için döngü inanıyoruz ve contains ve add çünkü onun karma göre grubu, sabit bir zaman gerekir. Tüm kümede arama yapmak için karma tabanlı ve gerekli yineleme olmasaydı, üst sınır n^2 olur.

Tamsayılar değişmezdir, bu yüzden alan karmaşıklığı 2n olacaktır, ki sadece n'ye basitçe inanıyorum, çünkü sabitlerin önemi yoktur.

Dizide nesneler varsa ve ayarladıysanız, 2n referansları ve n nesnelerine sahip olursunuz, bu nedenle 3n'daysınız, bu da hala doğrusaldır (zaman sabittir) boşluk kısıtlamaları.

EDIT-- yep "Bu sınıf, temel işlevlerin (ekleme, kaldırma, içerme ve boyut) sabit bir zaman performansı sunarak, karma işlevinin öğeleri kovalar arasında düzgün bir şekilde dağıttığı varsayılır."

Bkz. here.