一种改进的随机选择算法

• 作者: 周鹏
• 来源期刊: 三峡大学学报（自然科学版）
• 学科: 工学
• 关键词: 选择算法 随机算法 期望 时间复杂度
• 年，卷（期）: 2007,（5）
• 所属期刊栏目: 数理研究
• 页码范围: 470-473
• 页数: 4页
• 分类号: TP301.5
• 字数: 3334字
• 语种: 中文
• DOI: 10.3969/j.issn.1672-948X.2007.05.023

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	周鹏	三峡大学理学院	6	6	1.0	2.0