一种改进的随机选择算法

摘要：

在一组数据中寻找第k小元素是一个常见的问题.确定性算法可以在Θ(n)的时间内完成,但是却有一个很大的常数使得算法不太实用.源于Hoare的随机选择算法可以使得算法执行比较的期望次数小于4n.改进算法中随机选择分组元素的方法,将使新算法在数据为均匀分布时执行比较的期望次数小于3n.

关键词：选择算法、随机算法、期望、时间复杂度

所属期刊栏目：29

分类号：TP301.5(计算技术、计算机技术)

在线出版日期：2008-01-14（万方平台首次上网日期，不代表论文的发表时间）

页数：共4页

页码：470-473