文章基本信息

标题：Selecting the median
本地全文：下载
作者：Dorit Dor, Uri Zwick
期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：1995
卷号：1995
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：Improving a long standing result of Sch\"{o}nhage, Paterson and Pippenger we show that the MEDIAN of a set containing n elements can always be found using at most 2.95n comparisons. This is the full version of the paper. An extended abstract version of the paper apperead in the proceedings SODA'95.
关键词：Comparison Algorithms, Order Statistics, Selection Algorithms