Algorithmen und Datenstrukturen · Senior · Frage 68 von 75
Was bringt Randomisierung für Quicksort?
- 1Stabilität für Elemente mit gleichen Schlüsseln
- 2Erwartetes O(n log n) für jede Eingabe
- 3Garantiert O(n log n) im schlimmsten Fall für jede Eingabe
Antwort zeigen
Richtige Antwort: Erwartetes O(n log n) für jede Eingabe
Erklärung
Mit zufälligem Pivot ist keine feste Eingabe dauerhaft schlecht, die Erwartung gilt also für jede Eingabe, auch für bösartige. Der schlimmste Fall bleibt möglich, nur extrem unwahrscheinlich.