Algorithmen und Datenstrukturen · Senior · Frage 16 von 75
Welche durchschnittliche Komplexität hat Quickselect beim Finden des k-kleinsten Elements?
- 1O(log n)
- 2O(n log n)
- 3O(n)
Antwort zeigen
Richtige Antwort: O(n)
Erklärung
Wie Quicksort teilt es auf, rekursiert aber nur in die Seite, die Position k enthält, die Arbeit ist also n + n/2 + n/4 + ... ≈ 2n. Der schlimmste Fall ist O(n²); Median of Medians garantiert O(n) mit größerer Konstante.