Exponential bounds for the running time of a selection algorithm
作者：
Highlights：
•
摘要
Hoare's selection algorithm for finding the kth-largest element in a set of n elements is shown to use C comparisons where 1.(i) E(Cp) ⩽ Apnp for some constant Ap > 0 and all p ⩾ 1;2.(ii) P(Cn ⩾ u) ⩽ (34)u(1 + o(1)) as u → ∞. Exact values for the “Ap” and “o(1)” terms are given.
论文关键词：
论文评审过程：Received 20 March 1982, Revised 4 May 1983, Available online 2 December 2003.
论文官网地址：https://doi.org/10.1016/0022-0000(84)90009-6
