Algorithmen und Datenstrukturen · Middle · Frage 3 von 75
Was ist der schlimmste Fall von Quicksort, und wann tritt er ein?
- 1O(n²), wenn Pivots das Array immer sehr ungleich teilen
- 2O(n log n), wenn das Array viele Duplikate enthält
- 3O(n), wenn die Eingabe zufällig schon sortiert ist
Antwort zeigen
Richtige Antwort: O(n²), wenn Pivots das Array immer sehr ungleich teilen
Erklärung
Ist das Pivot immer das kleinste oder größte Element (etwa das erste Element eines sortierten Arrays), entfernt jede Aufteilung nur ein Element. Zufällige Pivots oder Median-of-three machen das unwahrscheinlich; der Durchschnitt ist O(n log n).