Algorithmus für nth_element [geschlossen]
-
25-09-2019 - |
Frage
Ich habe vor kurzem festgestellt, dass ein Verfahren existiert namens nth_element in der STL. Um die Beschreibung zu zitieren:
ist nth_element ähnlich wie partial_sort, dass er teilweise in ordnet eine Reihe von Elementen: es ordnet den Bereich [first, last), wie dass das Element, auf die der zu Iterator ist nth das gleiche wie die Element, das in dieser Position sein würde, wenn der gesamte Bereich [first, last) hatte wurden sortiert. Darüber hinaus keine der Elemente im Bereich [n-ten, liest) ist weniger als alle der Elemente in der Bereich [first, n-te).
Sie behauptet, O (n) Komplexität im Durchschnitt zu haben. Wie funktioniert der Algorithmus funktioniert? Ich konnte keine Erklärung dafür finden.
Lösung
Es ist eine Auswahl Algorithmus genannt und wikipedia hat eine gute Seite darauf: http: //en.wikipedia. org / wiki / Selection_algorithm
Auch über Auftragsstatistik lesen: http://en.wikipedia.org/wiki/Order_statistic
Andere Tipps
Wahrscheinlich der Median-of-Mediane Algo.