Diskussion:Quickselect

aus Wikipedia, der freien Enzyklopädie
Letzter Kommentar: vor 4 Jahren von Jonathan Haas in Abschnitt Vorteil gegenüber linearer Suche?
Zur Navigation springen Zur Suche springen

Vorteil gegenüber linearer Suche?

[Quelltext bearbeiten]

Ich hab es bestimmt falsch verstanden. Aber eine unsortierte Liste linear zu durchsuchen hat ebenfalls eine Laufzeit von O(n). Inwiefern ist Quickselect dann besser? --HB Jepsen (Diskussion) 18:12, 28. Mär. 2020 (CET)Beantworten

Wie findest du denn mit einer normalen linearen suche das k-kleinste (also z. B. viert-kleinste, sechst-kleinste, hundertelft-kleinste usw.) Element? Oder z. B. den Median in einer unsortieren Liste von Zahlen? Intuitiv müsste man die Liste sortieren und das k-te Element nehmen, aber mit Quickselect geht das schneller. -- Jonathan 19:34, 29. Mär. 2020 (CEST)Beantworten