Beste Antwort
Wenn Sie über ausreichende Kenntnisse der Funktionsweise der schnellen Sortierung verfügen, z Das gleiche rekursiv für jedes Subarray ist es einfach, die Zeitkomplexität unter Berücksichtigung der folgenden Aspekte zu analysieren:
Schlimmster Fall:
Der schlimmste Fall tritt auf, wenn bei jeder Rekursion der nächste Drehpunkt für geteilte Arrays am Ende des Arrays liegt.
Wenn N. ist die Länge des Arrays und hat einen aktuellen Drehpunkt an der Startposition des Arrays.
Drehpunkt am letzten Index wird nur beim Durchlaufen des Arrays von Anfang bis Ende identifiziert. Nach dem Fixieren des Pivots und dem Aufteilen der resultierenden Teilarrays der Länge sind (N-1), 1 .
Wieder dieses (N-1) -Unterarray findet den nächsten Pivot am letzten Index, der zu Array-Partitionen mit den Längen (N-2), 1 span führt >.
Dieser Vorgang wird wiederholt, bis die endgültigen Längen der Unterarrays beide 1,1 sind.
Also, dies kann in Schritt 1 mathematisch als
in Papier gezeichnet werden: Mit N -Elementen beträgt die zeitliche Komplexität für diese Partition
T (N) = N + T (N-1)
Wobei T (N-1) die zeitliche Komplexität der Partition ist rekursiv verarbeitet werden und N ist die Zeit, die benötigt wird, um N Elemente mit einem festen Drehpunkt zu vergleichen.
in Schritt 2: mit N-1 Elementen ,
T (N-1) = (N-1) + T (N-2)
T (N-2) = (N-2) + T (N-3)
…
T (3) = 3 + T (2)
T (2) = 2 + T (1)
T ( 1) = 0, da die Zeit zum Partitionieren des Arrays mit der Länge 1 0 ohne Partitionen ist.
Daher
T (N) = N + (N-1) + (N-2) … + 3 + 2 ≈ N * (N + 1) / 2
= (N ^ 2) / 2
= O (N ^ 2)
Durchschnittlicher Fall :
Im Durchschnitt teilt der nächste Pivot das Array durch Vergleichen in zwei gleiche Längen auf (N / 2) alle Elemente, die zu zeitlicher Komplexität führen N.
T (N) = 2 * T (N / 2) + N
teilen beide Seiten durch N
T (N) / N = 2 * (T (N / 2) / N) + N / N
T (N) / N = 2 * (T. (N / 2) / N) + 1
Daher ist T (N) / N = (T (N / 2) / (N / 2)) + 1
P (N / 2) / (N / 2) = T (N / 4) / (N / 4) + 1
…
T (2) / 2 = T (1) / 1 + 1
As T (1) = 0
T (2) / 2 = 1
T (4) / 4 = T (2) + T. (1)
T (8) / 8 = T (4) + T (2) + T (1) ## log (n) Terme
Daher ist T (N) / N = log N
T (N) = NlogN
Antwort
QuickSort ist ein Divide and Conquer-Algorithmus. Es wählt ein Element als Drehpunkt aus und partitioniert das angegebene Array um den ausgewählten Drehpunkt. Es gibt viele verschiedene Versionen von quickSort, die Pivot auf unterschiedliche Weise auswählen.
- Wählen Sie immer das erste Element als Pivot aus.
- Wählen Sie immer das letzte Element als Pivot aus (implementiert) unten)
- Wählen Sie ein zufälliges Element als Pivot aus.
- Wählen Sie den Median als Pivot aus.
Der Schlüsselprozess in quickSort ist eine Partition ( ). Das Ziel von Partitionen besteht darin, bei einem Array und einem Element x des Arrays als Drehpunkt x an der richtigen Position in einem sortierten Array zu platzieren und alle kleineren Elemente (kleiner als x) vor x und alle größeren Elemente (größer) zu setzen als x) nach x. All dies sollte in linearer Zeit erfolgen.
Die Schritte der Quicksortierung sind:
Step 1 − Choose the highest index value has a pivot
Step 2 − Take two variables to point left and right of the list excluding pivot
Step 3 − left points to the low index
Step 4 − right points to the high
Step 5 − while value at left is less than pivot move right
Step 6 − while value at the right is greater than pivot move left
Step 7 − if both step 5 and step 6 does not match swap left and right
Step 8 − if left ≥ right, the point where they met is the new pivot
Implementierung von Quicksort:
Quicksort(A,p,r) {
if (p
q
Quicksort(A,p,q)
Quicksort(A,q+1,r)
}
}
Partition(A,p,r)
x
i
j
while (True) {
repeat
j
until (A[j]
i
until (A[i] >= x)
if (i A[j]
else
return(j)
}
}
Zeitliche Komplexität von Quicksort:
Am schlimmsten Fall: Der schlimmste Fall tritt auf, wenn der Partitionsprozess immer das größte oder kleinste Element als Drehpunkt auswählt. Wenn wir die obige Partitionsstrategie betrachten, bei der das letzte Element immer als Drehpunkt ausgewählt wird, tritt der schlimmste Fall auf, wenn das Array bereits in aufsteigender oder absteigender Reihenfolge sortiert ist. Es folgt eine Wiederholung für den schlimmsten Fall.
T(n) = T(0) + T(n-1) + (n)
which is equivalent to
T(n) = T(n-1) + (n)
Die Komplexität der obigen Wiederholung ist n Quadrat
Bester Fall: Der beste Fall tritt auf, wenn der Partitionsprozess immer auswählt das mittlere Element als Drehpunkt. Es folgt eine Wiederholung für den besten Fall.
T(n) = 2T(n/2) + (n)
Die Komplexität der obigen Wiederholung ist nLogn
Durchschnittlicher Fall: Um eine durchschnittliche Fallanalyse durchzuführen, müssen wir alle möglichen Permutationen des Arrays berücksichtigen und die Zeit berechnen, die jede Permutation benötigt, die nicht einfach aussieht. Wir können uns ein Bild vom Durchschnittsfall machen, indem wir den Fall betrachten, in dem die Partition O (n / 9) -Elemente in eine Menge und O (9n / 10) -Elemente in andere Mengen einfügt. Es folgt eine Wiederholung für diesen Fall.
T(n) = T(n/9) + T(9n/10) + (n)
Die Komplexität der obigen Wiederholung ist nLogn
Raumkomplexität von Quicksort :
Der von Quicksort verwendete Speicherplatz hängt von der verwendeten Version ab.
Die In-Place-Version von Quicksort hat eine Speicherplatzkomplexität von O (log n), auch in Der schlimmste Fall, wenn es sorgfältig mit den folgenden Strategien implementiert wird:
- In-Place-Partitionierung wird verwendet. Diese instabile Partition benötigt O (1) Speicherplatz.
- Nach der Partitionierung wird die Partition mit den wenigsten Elementen zuerst (rekursiv) sortiert, wobei höchstens O (log n) Speicherplatz benötigt wird. Dann wird die andere Partition unter Verwendung einer Schwanzrekursion oder -iteration sortiert, die nicht zum Aufrufstapel hinzugefügt wird. Diese Idee wurde, wie oben diskutiert, von R. Sedgewick beschrieben und hält die Stapeltiefe durch O (log n) begrenzt / li>