En iyi durumda takas ve karşılaştırma için İkili Ekleme sıralama karmaşıklığı

Question

İkili eklemeli sıralama için karmaşıklık ne olabilir? Ve kaç tane takas ve karşılaştırma yapılıyor?

O(n(LG n))Karşılaştırma olabilir ama emin değilim. En kötü durum için, gerçekten N^2takas. En iyisi ne olacak?

Answer 1

bisect_leftVe list.pop(..)ve gibi yerleşik işlevlerden yararlanarak ikili ekleme sıralamayı kolayca yazabilirsiniz list.insert(..):

def bininssort(L):
    n = len(L)
    i,j=0,0
    for i in range(1,n):
        j=i-1
        x=L.pop(i)
        i1=bisect_left(L,x,0,j+1)
        L.insert(i1,x)
    return L

En kötü durumda Hakkında en beri i-thdöngünün yineleme, biz alt-dizide içindeki bir ikili arama yapmak A[0..i]ile 0<=i<natması gerektiğini log(i)biz şimdi yerde bir öğe eklemek zorunda biliyorum, operasyonlar i1ve biz bunun insert, ancak yerleştirme, onu takip eden tüm öğeleri bir konum sağa itmemiz gerektiği anlamına gelir ve bu en azından n-iişlemdir ( n-iyerleştirme konumuna bağlı olarak işlemlerden daha fazlası olabilir ). Sadece bu ikisini özetlersek\sum_{i=1}^n log(i) + (n-i) = log(n!) + (n*(n+1))/2 ~ n*log(n) + (n*(n+1))/2

(Yukarıda Stirling yaklaşım arasında log(n!)kullanılmaktadır)

Şimdi wiki sayfası diyor ki

Genel bir kural olarak, herhangi bir işlevdeki en yüksek dereceden terimin büyüme oranına hakim olduğu ve bu nedenle çalışma zamanı sırasını tanımladığı varsayılabilir.

Bu yüzden, en kötü durumda, ikili yerleştirme sıralamanın O(n^2)karmaşık olduğu sonucunun çıkarılacağını düşünüyorum .

Ayrıca bakınız:

• ikili aramayı kullanarak ekleme sıralaması
• ikili aramayla ekleme sıralaması
• ikili ekleme sıralaması analizi
• ikili ekleme sıralaması ve karmaşıklığı

Sonra tersine çevrilmiş ( n,n-1,n-2,..,1) ve değişen ( 0,n-1,1,n-2,2,n-3,...) listelerde nasıl performans gösterdiğini kontrol etmeye çalıştım . Ve onları ( matchgrowth modülünü kullanarak ) farklı büyüme oranlarına uydurdum , bu kısım sadece bir tahmin. Ters sıra, polinom zamana uyduruldu ve alternatif sıra, yarı doğrusal zamana uyduruldu

En iyi durum burada açıklanmıştır . Liste halihazırda sıralıysa, o zaman herhangi bir takas yapmasak bile, tüm ikili aramalar hala gerçekleştirilmektedir, bu da O(n*log(n)).

Burada kullanılan kod bu depoda mevcuttur .