Schreiber, C. (2011). Über das Verhalten von Quickselect [Diploma Thesis, Technische Universität Wien]. reposiTUm. http://hdl.handle.net/20.500.12708/160162
E104 - Institut für Diskrete Mathematik und Geometrie
-
Date (published):
2011
-
Number of Pages:
72
-
Keywords:
Quickselect; Analyse
de
Quickselect; analysis
en
Abstract:
Eine Analyse verschiedene Varianten von Quickselect: Standard QS, Relaxed QS (Suche nach einem Element aus einem Toleranzintervall), Multiple QS (Suche nach mehreren Elementen gleichzeitig), Relaxed Multiple QS (Suche nach mehreren Elementen mit jeweils unterschiedlichen Toleranzintervallen). Unter anderem wird die Anzahl der Bewegungen von Elementen, die Anzahl an Aufrufe sowie die Anzahl der Vergleiche betrachtet und einige asymptotische Resultate angegeben.<br />Als Basis dient eine Lösung für eine trivariate Rekursion, welche mit Hilfe von erzeugenden Funktionen gelöst wird. Schließlich wird noch der Zusammenhang zu binären Suchbäumen behandelt, bei denen einige Parameter den bereits Betrachteten entsprechen.
de
An analysis of variants of quickselect: normal QS, relaxed QS (find an Element that is within a certain tolerance limit), multiple QS (simultaneously find a number of elements), relaxed multiple QS (simultaneously find a number of elements each with its own tolerance limit).<br />Among others we take a look at the number of moves, the number of procedure calls and the number of comparisons and also give asymptotic results.<br />At the core of the work is a solution for a generic trivariate sum, which is solved via generating functions.<br />Finally certain properties of binary search trees are considered, which mirror the results from Quickselect.
en
Additional information:
Abweichender Titel laut Übersetzung der Verfasserin/des Verfassers
