Komplexität der Sortierung von binären Einfügungen für Swaps und Vergleiche im besten Fall

Question

Was könnte die Komplexität für die Sortierung von binären Einfügungen sein? Und wie viele Swaps und Vergleiche werden durchgeführt?

Es könnten O(n(LG n))Vergleiche sein, aber ich bin mir nicht sicher. Im schlimmsten Fall handelt es sich tatsächlich um N^2Swaps. Was ist mit den Besten?

Answer 1

Sie können die Sortierung von binären Einfügungen einfach schreiben, indem Sie integrierte Funktionen wie bisect_leftund list.pop(..)und nutzen 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

Über den schlimmsten Fall, da i-thwir bei der Iteration der Schleife eine binäre Suche innerhalb des Sub-Arrays durchführen A[0..i], mit 0<=i<nder log(i)Operationen ausgeführt werden sollen, sodass wir jetzt wissen, dass wir ein Element an der Stelle i1einfügen müssen und es einfügen, aber Das Einfügen bedeutet, dass wir alle darauf folgenden Elemente um eine Position nach rechts verschieben müssen, und das sind mindestens n-iOperationen ( n-ije nach Einfügeort können es mehr als Operationen sein). Wenn wir nur diese beiden zusammenfassen, erhalten wir\sum_{i=1}^n log(i) + (n-i) = log(n!) + (n*(n+1))/2 ~ n*log(n) + (n*(n+1))/2

(in der obigen Stirling-Näherung von log(n!)wird verwendet)

Jetzt die Wiki - Seite sagt

Als Faustregel kann man annehmen, dass der Term höchster Ordnung in einer bestimmten Funktion seine Wachstumsrate dominiert und somit seine Laufzeitreihenfolge definiert

Ich denke also, die Schlussfolgerung wäre, dass im schlimmsten Fall die binäre Einfügungssortierung komplex ist O(n^2).

Siehe auch:

• Einfügesortierung mit binärer Suche
• Einfügesortierung mit binärer Suche
• Analyse der binären Einfügungssortierung
• Sortierung und Komplexität der binären Einfügung

Dann habe ich versucht zu überprüfen, wie es auf umgekehrten ( n,n-1,n-2,..,1) und alternierenden ( 0,n-1,1,n-2,2,n-3,...) Listen funktioniert . Und ich habe sie (unter Verwendung des Matchgrowth-Moduls ) an unterschiedliche Wachstumsraten angepasst. Dieser Teil ist nur eine Annäherung. Die umgekehrte Reihenfolge wurde an die Polynomzeit angepasst, und die alternierende Reihenfolge wurde an die quasilineare Zeit angepasst

Der beste Fall wird hier erklärt . Wenn die Liste bereits sortiert ist, werden auch dann, wenn wir keine Swaps durchführen, alle binären Suchen durchgeführt, was dazu führt O(n*log(n)).

Der hier verwendete Code ist in diesem Repository verfügbar .