Quicksort-Laufzeit

Ich versuche, mein Wissen über Algorithmenanalyse aufzufrischen (und hoffentlich mehr zu lernen). Ich habe vor zwei Jahren einen Kurs dazu gemacht, aber ich versuche, das aufzuholen, was ich damals gelernt habe.

Ich gehe dabei vor, indem ich Übungen aus dem klassischen Text Introduction to Algorithms, 2nd Edition – CLRS mache.

Das Problem, das ich zu lösen versuche, ist folgendes:

Aufgabe 7.2-2
Wie lange läuft QUICKSORT, wenn alle Elemente von Array A denselben Wert haben?

Meine Lösung
Die Laufzeit von QUICKSORT, wenn alle Elemente von Array A den gleichen Wert haben, entspricht der Ausführung von QUICKSORT im schlimmsten Fall, da QUICKSORT unabhängig davon, welcher Pivot ausgewählt wird, alle Werte in A durchlaufen muss. Und da alle Werte gleich sind, führt jeder rekursive Aufruf zu einer unausgeglichenen Partitionierung.

Somit wird die Wiederholung sein:

T ( N ) = T ( N − 1 ) + Θ ( N )

Die obige Wiederholung hat die Lösung (ich werde dies später beweisen):

T ( N ) = Θ ( N 2 )

Daher ist die Laufzeit von QUICKSORT in diesem Fall

Θ ( N 2 )

Bitte überprüfen Sie, ob ich die Frage richtig beantwortet habe :)

Bitte teilen Sie mir mit, ob diese Frage an anderer Stelle im SE-Netzwerk veröffentlicht werden soll.

Danke!

Jake Clawson

Das ist richtig.
@Emre: Das ist kein guter Vorschlag. cstheory.SE ist für Fragen auf Forschungsebene gedacht , was diese hier definitiv nicht ist, also würde sie mit einem Schlag herabgestimmt und geschlossen werden. Das macht es natürlich nicht zu einer schlechten Frage, im Gegenteil!
Es ist üblicher (AFAIK), Großbuchstaben zu verwenden Θ statt Kleinbuchstaben θ für "Big-Theta"-Notation.
Die Probleme 7-1 zu CLRS geben ein Hoare-Implement von Quicksort. Die Laufzeit von Hoare's ist Θ ( N Protokoll ⁡ N ) wenn alle Elemente den gleichen Wert haben.
Völlig ok.

Antworten (3)

Deine Lösung sieht völlig richtig aus.

Die Antwort hängt davon ab, wie Sie den Drehpunkt auswählen. Wenn Sie dem im CLSR vorhandenen Algorithmus folgen, der immer das letzte Element als Drehpunkt auswählt, würde dies zu der Gleichung führen T ( N ) = T ( N − 1 ) + N und daher T ( N ) = Ö ( N 2 ) Andernfalls, wenn Sie jedes Mal das mittlere Element als Drehpunkt auswählen, wird die Gleichung T ( N ) = 2 T ( N / 2 ) + N was dazu führen würde T ( N ) = Θ ( N Protokoll ⁡ N ) .

Die Art und Weise, wie der Drehpunkt gewählt wird, ist völlig irrelevant, da alle Werte gleich sind. Es ist nur der Partitionierungsprozess, der sicherstellen kann, dass die Partition ausgeglichen ist. Dafür ist es wesentlich, dass die Vergleiche eher nicht streng als streng sind.

Nein, die Partitionierungen führen zu perfekt ausbalancierten Subarrays. Tatsächlich sucht der Algorithmus nach dem ersten Element ≥ nach links schwenken und ≤ nach rechts schwenken und vertauschen. Da alle Elemente gleich (und gleich dem Pivot) sind, werden das Element ganz links und ganz rechts sofort vertauscht. Dies wird so lange fortgesetzt, bis sich die beiden Indizes treffen, was genau in der Mitte der Fall ist.

Quicksort-Laufzeit
AntwortenHierDatenschutz-Bestimmungen1y, 0v