Complessità di ordinamento dell'inserimento binario per gli scambi e il confronto nel migliore dei casi

Question

Quale potrebbe essere la complessità per l'ordinamento per inserzione binaria? E quanti scambi e confronti vengono effettuati?

Potrebbe essere un O(n(LG n))confronto, ma non ne sono sicuro. Nel peggiore dei casi, si tratta davvero di N^2swap. E il meglio?

Answer 1

Puoi scrivere facilmente l'ordinamento per inserzione binaria sfruttando le funzioni integrate come bisect_lefte list.pop(..)e 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

Circa il caso peggiore, poiché i-thall'iterazione del ciclo, eseguiamo una ricerca binaria all'interno del sotto-array A[0..i], con 0<=i<n, che dovrebbe richiedere log(i)operazioni, quindi ora sappiamo che dobbiamo inserire un elemento nella posizione i1e lo inseriamo, ma l'inserimento significa che dobbiamo spingere tutti gli elementi che lo seguono di una posizione verso destra, e questo è almeno n-ioperazioni (può essere più che n-ioperazioni a seconda della posizione di inserimento). Se riassumiamo solo questi due, otteniamo\sum_{i=1}^n log(i) + (n-i) = log(n!) + (n*(n+1))/2 ~ n*log(n) + (n*(n+1))/2

(in quanto sopra viene utilizzata l'approssimazione di Stirlinglog(n!) )

Ora la pagina wiki dice

Come regola empirica, si può presumere che il termine di ordine più elevato in una data funzione domini il suo tasso di crescita e quindi definisce il suo ordine di esecuzione

Quindi penso che la conclusione sarebbe che nel peggiore dei casi l'ordinamento per inserzione binaria ha una O(n^2)complessità.

Guarda anche:

• ordinamento per inserzione utilizzando la ricerca binaria
• ordinamento per inserzione con ricerca binaria
• analisi dell'ordinamento per inserzione binaria
• ordinamento e complessità dell'inserimento binario

Quindi ho provato a verificare come si comporta sugli elenchi reversed ( n,n-1,n-2,..,1) e alternating ( 0,n-1,1,n-2,2,n-3,...). E li ho adattati (usando il modulo matchgrowth ) a diversi tassi di crescita, questa parte è solo un'approssimazione. L'ordine inverso è stato adattato al tempo polinomiale e l'ordine alternato è stato adattato al tempo quasilineare

Il caso migliore è spiegato qui . Se l'elenco è già ordinato, anche se non eseguiamo scambi, tutte le ricerche binarie vengono comunque eseguite, il che porta a O(n*log(n)).

Il codice qui utilizzato è disponibile in questo repository.