<div class="csl-bib-body">
<div class="csl-entry">Schreiber, C. (2011). <i>Über das Verhalten von Quickselect</i> [Diploma Thesis, Technische Universität Wien]. reposiTUm. http://hdl.handle.net/20.500.12708/160162</div>
</div>
-
dc.identifier.uri
http://hdl.handle.net/20.500.12708/160162
-
dc.description
Abweichender Titel laut Übersetzung der Verfasserin/des Verfassers
-
dc.description.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
dc.description.abstract
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
dc.language
Deutsch
-
dc.language.iso
de
-
dc.subject
Quickselect
de
dc.subject
Analyse
de
dc.subject
Quickselect
en
dc.subject
analysis
en
dc.title
Über das Verhalten von Quickselect
de
dc.title.alternative
Properties of quickselect
en
dc.type
Thesis
en
dc.type
Hochschulschrift
de
dc.contributor.affiliation
TU Wien, Österreich
-
tuw.thesisinformation
Technische Universität Wien
-
tuw.publication.orgunit
E104 - Institut für Diskrete Mathematik und Geometrie
