Hat Quicksort immer eine quadratische Laufzeit, wenn Sie ein maximales Element als Drehpunkt auswählen?

9

Wenn Sie einen Schnellsortieralgorithmus haben und immer das kleinste (oder größte) Element als Drehpunkt auswählen; Habe ich Recht, wenn Sie einen bereits sortierten Datensatz bereitstellen, erhalten Sie immer die schlechteste Leistung, unabhängig davon, ob Ihre "bereits sortierte" Liste in aufsteigender oder absteigender Reihenfolge vorliegt?

Ich denke, wenn Sie immer das kleinste Element für Ihren Pivot auswählen, spielt es keine Rolle, ob Ihre 'bereits sortierte' Eingabe nach aufsteigend oder absteigend sortiert ist, da die Teilmenge, die relativ zu Ihrem Pivot sortiert werden soll, immer die ist gleiche Größe?

algorithms time-complexity algorithm-analysis runtime-analysis sorting Yoonsi
quelle

2

Ihr Denken ist richtig, aber Sie können in diesem Fall auch direkt argumentieren und die Laufzeit von Quicksort berechnen - Sie erhalten .

O (n^{2})

$O(n^2)$

Yuval Filmus

15

Die Worst-Case-Komplexität für Quicksort ist . Dies wird erreicht, indem Drehpunkte ausgewählt werden, die die Menge so teilen, dass eine Gruppe nur ein einziges Mitglied hat. Mit einem schlechten Pivot-Picking-Algorithmus kann dies leicht erreicht werden, indem ein Ende eines sortierten Satzes ausgewählt wird. Ihre Annahme ist richtig. $\Theta(n^2)$

Walrii
quelle

2

Es war besser, es zu schreiben: "... Dies wird erreicht, indem Drehpunkte ausgewählt werden, die die Menge so teilen, dass eine Gruppe nur ein O (1)

@Saeed Amiri: Das stimmt, aber es ist besser, genau zu sein.

MMS

1

@SaeedAmiri: O (1) gibt an, dass es proportional zu 1 ist, was bedeutet, dass es k * 1 sein kann. Der tatsächliche schlimmste Fall wird erreicht, wenn er genau 1 ist. Ich gebe Ihnen zu, dass O (1) immer noch zu O (n ^ 2) führen kann.

Walrii

@MMS, ich habe , um genau zu sein, walrii Sie haben geschrieben: "Die Worst-Case-Komplexität für Quicksort ist ..", aber tatsächlich der einzige Weg, um ist nicht die Art, wie du es gesagt hast, ja, die Art, wie du sie beschrieben hast, ist der schlimmste Fall überhaupt, aber nicht die einzige .

O (1)

$O(1)$

Θ (n^{2})

$\Theta (n^2)$

Θ (n^{2})

$\Theta(n^2)$

Θ (n^{2})

$\Theta (n^2)$

5

Ja! Du denkst, es ist absolut richtig! Und wie von Yuval Filmus richtig erwähnt, wird die Laufzeit $\Theta(n^2)$

n0nChun
quelle

3

Ein Subarray hat oder Element, während das andere Elemente hat; daher ist es : $0$ $1$ $(n-1)$ $O(n^2)$

t (n) = t (n - 1) + t (0) + O (n) = O (n^{2})

$t(n)=t(n-1)+t(0)+O(n)= O(n^2)$

Sulava
quelle

Hat Quicksort immer eine quadratische Laufzeit, wenn Sie ein maximales Element als Drehpunkt auswählen?

Antworten: