Zeitaufwand für Shell-Sortierung?

Question

Zuerst, hier ist mein Shell Bankleitzahl (mit Java):

public char[] shellSort(char[] chars) { 
    int n = chars.length; 
    int increment = n/2; 
    while(increment > 0) { 
     int last = increment; 
     while(last < n) { 
      int current = last - increment; 
      while(current >= 0) { 
       if(chars[current] > chars[current + increment]) { 
        //swap 
        char tmp = chars[current]; 
        chars[current] = chars[current + increment]; 
        chars[current + increment] = tmp; 
        current -= increment; 
       } 
       else { break; } 
      } 
      last++; 
     } 
     increment /= 2; 
    } 
    return chars; 
} 

Ist dies eine korrekte Umsetzung der Shell Art (zu vergessen, jetzt über die effizienteste Lücke Sequenz - zB 1,3,7,21. ..)? Ich frage, weil ich gehört habe, dass die für Shell Sort am besten geeignete Zeitkomplexität O (n) ist. (Siehe http://en.wikipedia.org/wiki/Sorting_algorithm). Ich kann nicht sehen, dass diese Effizienz durch meinen Code realisiert wird. Wenn ich ihm Heuristiken hinzugefügt habe, dann ja, aber so wie es steht, nein.

Das heißt, meine Hauptfrage jetzt - ich habe Schwierigkeiten bei der Berechnung der Big O Zeit Komplexität für meine Shell-Sortimplementierung. Ich habe festgestellt, dass die äußerste Schleife als O (log n), die mittlere Schleife als O (n) und die innerste Schleife auch als O (n) ist, aber ich erkenne, dass die inneren zwei Schleifen nicht wirklich O sind (n) - sie wären viel weniger als das - was sollten sie sein? Denn offensichtlich läuft dieser Algorithmus viel effizienter als O ((log n) n^2).

Jede Anleitung wird sehr geschätzt, da ich sehr verloren bin! : P

Answer 1

Der schlechteste Fall Ihrer Implementierung ist Θ (n^2) und der beste Fall ist O (nlogn), was für Shell-Sortierung sinnvoll ist.

Der beste Fall ε O (n log n):

Das am besten Fall ist, wenn das Array bereits sortiert ist. Das würde bedeuten, dass die innere if-Anweisung niemals wahr sein wird, was die innere while-Schleife zu einer konstanten Zeitoperation macht. Die Verwendung der Grenzen, die Sie für die anderen Schleifen verwendet haben, ergibt O (nlogn). Der beste Fall von O (n) wird erreicht, indem eine konstante Anzahl von Inkrementen verwendet wird.

Der schlimmste Fall ε O (n^2):

Ihre obere Schranke Gegeben Sie für jede Schleife erhalten O ((log n) n^2) für den ungünstigsten Fall. Aber fügen Sie eine weitere Variable für die Lückengröße g hinzu. Die Anzahl der in der inneren Zeit benötigten Vergleiche/Austauschvorgänge ist jetzt < = n/g. Die Anzahl der Vergleiche/Austauschvorgänge der Mitte ist < = n^2/g. Addiere die obere Grenze der Anzahl der Vergleiche/Austauschvorgänge für jede Lücke zusammen: n^2 + n^2/2 + n^2/4 + ... < = 2n^2 & epsi; O (n^2). Dies entspricht der bekannten Worst-Case-Komplexität für die Lücken, die Sie verwendet haben.

Der ungünstigste Fall ε Ω (n^2):

des Arrays betrachtet, bei dem alle geraden positionierte Elemente größer ist als der Medianwert sind. Die ungeraden und geraden Elemente werden nicht verglichen, bis wir das letzte Inkrement von 1 erreicht haben. Die Anzahl der Vergleiche/Austauschvorgänge, die für die letzte Iteration benötigt werden, ist Ω (n^2).