zaman karmaşıklığı

Question

Yinelediğim bir dizi listesi var. Her yineleme ben bir elementi elde etmek get() diyoruz ve bu madde bazı koşul geçerse, ben zaman karmaşıklığı burada ne olduğundan emin değilim add()

List<Item> items = new ArrayList<Item>(); 
List<Item> lessItems = new ArrayList<Item>(); 
for(int index = 0; index < items.size(); index++){ 
    Item toCheck = items.get(i); 
    if(toCheck meets some condition){ 
     lessItems.add(toCheck); 
    } 
} 

kullanarak yeni dizi listesine eklenir. Tüm öğeler için get() öğesini çağırıyorum, yani O (n). Daha sonra, potansiyel olarak tüm öğeler üzerinde add() öğesini çağırıyorum, böylece başka bir O (n) var. Bu konuda fazla emin değilim.

Answer 1

Büyük O ve benzeri gösterimler, zaman karmaşıklığında asimptotik sınırlardır. Sayısal katsayıyı ortadan kaldırırlar ve çalışma zamanını giriş büyüklüğünün bir fonksiyonu olarak tahmin etmek için kullanılırlar.

2*n, 3*n, vb. O(n) ve 2*nlog(n), 3*nlog(n), vb. olarak temsil edilir. O(nlog(n)) olarak temsil edilir.

eklenti() işlemi, bu durumda sadece bir eleman ekler yana

, çalışma zamanı, diğer bir deyişle j*n veya O(n) içinde, (some constant)j*(n+some constant(k)) toplam çalışma süresini veren, yaklaşık (some small constant)k*1 olup. Bu durumda, ve bu tür tüm benzer durumlarda

, N çarpılır herhangi bir sabit k zamanını anlamına O(n) olarak temsil edilen giriş ArrayList'in boyutu ile doğrusal olarak değişmektedir.

Answer 2

Diğer tüm yanıtlar hatalı burada.

1. items liste yineleme için İlk döngü: karmaşıklığı listesinin lessItems sonuna kadar O(n)
2. takın her öğedir: Diğerleri söylediği gibi, normal dizide o O(n) olacak. Ancak Java, amortized array kullanarak ArrayList için uygular. Bu, dizinin sonuna eklerken algoritmanın yalnızca Amortized O(1) maliyetini ifade ettiği anlamına gelir. Yoksa O(1)

söyleyebiliriz Yani kod karmaşıklığı geçerli: O(n) * amortized O(1).

dynamic array

Ek bilgi 1: Kısaca O(n)

başka referans

toplam karmaşıklığı O(N^2) yani dizinin sonundaki sokulması karmaşıklığı, O(N) ise değil, O (2 * N) diğer cevaplar gibi söyledi. eklemek için toplam karmaşıklığı olacağından: 1 + 2 + 3 + ...+ n = n*(n+1)/2

Addtional Not 2:

official document olarak belirtir:

boyut, isEmpty olsun, set, yineleyici ve listIterator işlemleri çalıştırmak sabit zamanda.Ekleme işlemi,, amortize edilmiş sabit zamanda çalışır; bu, n elemanlarının eklenmesi, O (n) zamanını gerektirir. Diğer işlemlerinin tümü doğrusal zamanda çalışır (kabaca). Sabit Faktör , LinkedList uygulaması için olanla karşılaştırıldığında düşük.

Ek not 3: kaynak kodu olarak

private void ensureExplicitCapacity(int minCapacity) { 
     modCount++; 

     // overflow-conscious code 
     if (minCapacity - elementData.length > 0) 
      grow(minCapacity); 
    } 

private void grow(int minCapacity) { 
     // overflow-conscious code 
     int oldCapacity = elementData.length; 
     int newCapacity = oldCapacity + (oldCapacity >> 1); 
     if (newCapacity - minCapacity < 0) 
      newCapacity = minCapacity; 
     if (newCapacity - MAX_ARRAY_SIZE > 0) 
      newCapacity = hugeCapacity(minCapacity); 
     // minCapacity is usually close to size, so this is a win: 
     elementData = Arrays.copyOf(elementData, newCapacity); 
    } 

programı eklediğinizde, söylemiştir: Burada

Ben resmi java kaynak kodundan almış grow yöntemin mantığı Mevcut kapasiteden daha büyük bir dizi boyut oluşturan eleman, Array büyütülebilir. Yetişkin bir dizinin yeni boyutta olacaktır:

int newCapacity = oldCapacity + (oldCapacity >> 1); 

Bu yerleştirme amortized O(1)

Answer 3

Bir yineleme yaptığını yapmak bir hile olduğunu ve O (n) yüzünden.

Ayrıca O olduğu bir ArrayList, öğe eklerken (1) (Amortized) bir dizin alma

da O (1).

Yaptığınız O (n) çarpı, O (1) işlemlerinin O (n).