Sabit boyutlu bir yığıntaki işlemlerin karmaşıklığı

Question

Yaklaşan bir sınav için çalışıyorum ve bir gelen sonsuz sayı akışından en yüksek 10 tamsayı oluşturmak ve sürdürmek zorunda kaldığım bir soruna rastladım. Minik bir sabit büyüklükte 10 kullanabileceğimi düşündüm ve yeni bir numara aldığımda, en azın yeni gelen numaradan daha düşük olup olmadığını kontrol edebilirdim, eğer öyleyse, yığını güncellemek zorunda kalırdım daha yüksek bir değer elde edinceye kadar kökün sırayla ayıklanması ve daha sonra atılan köklerin yanında (yeni boyutun (10) sabit boyutunu korumak için) eklenmesiyle. Şimdi bu yığına sahip olduğum için, yığıntaki her düğümü haşlatarak ve yazdırarak ilk 10'u kolayca alabilirim.

Java'da, PriorityQueue ile söylediklerimi gerçekleştirecek bir yöntem kodladım.

public void addNumber(int number){ 
    if(pq.size() < 10){ 
     pq.offer(number); 
    } 
    else if(pq.peek() < number){ 
     List<Integer> topNumbers = new LinkedList<Integer>(); 
     while(!pq.isEmpty() && pq.peek() < number){ 
      topNumbers.add(pq.poll()); 
     } 
     pq.offer(number); 
     for(int i = 1; i < topNumbers.size(); i++){ 
      pq.offer(topNumbers.get(i)); 
     } 
    } 
} 

public void printTop10(){ 
    List<Integer> topNumbers = new LinkedList<Integer>(); 
    while(!pq.isEmpty()){ 
     topNumbers.add(pq.poll()); 
    } 

    for(int i = 0; i < topNumbers.size(); i++){ 
     Node thisOne = topNumbers.get(topNumbers.size() - 1 - i); 
     System.out.println(thisOne); 
     pq.offer(thisOne); 
    } 
} 

Testlerime göre, bu kod işi yapar ve beklendiği gibi çalışır. Şimdi, benim sorum bu. Bu iki operasyon için karmaşıklık ne olurdu? Bir PriorityQueue'imiz var, bu yüzden insert ve extract-min işlemleri logaritmiktir. Fakat bu durumda, yığının boyutu, "n", en çok, 10'dur. Bu, karmaşıklığın o zaman temel olarak sabit O (1) zaman olan O (log 10) olduğu anlamına mı geliyor?

Answer 1

Evet; Bir sabitin logaritması da sabittir. Çoğunlukla, bu gibi algoritmalar, çalışma zamanlarını çeşitli değişkenlerin bir fonksiyonu olarak tanımlayarak analiz edilir. Örneğin, algoritmanızın, n numaralarının üstündeki k numaralarını O (n log k) saati ve O (k) boşluğundan çıkardığını söyleyebiliriz. Ancak, k değeri biliniyorsa, bu durumu analizimizi basitleştirmek için kullanabiliriz.