一种改进的随机选择算法  

An Improved Randomized Selection Algorithm

作　　者：周鹏[1] 

机构地区：[1]三峡大学理学院,湖北宜昌443002

出　　处：《三峡大学学报（自然科学版）》2007年第5期470-473,共4页Journal of China Three Gorges University：Natural Sciences

摘　　要：在一组数据中寻找第k小元素是一个常见的问题.确定性算法可以在Θ(n)的时间内完成,但是却有一个很大的常数使得算法不太实用.源于Hoare的随机选择算法可以使得算法执行比较的期望次数小于4n.改进算法中随机选择分组元素的方法,将使新算法在数据为均匀分布时执行比较的期望次数小于3n.A common problem is that of finding the No.k element in a set of data.An algorithm can solve this problem in Θ（n） asymptotic complexity;but it is impracticable for that there is a big constant digit.The randomized selection algorithm presented by Hoare can make the expectation of the times of comparing less than 4n.Improving the randomized selection pivot in the algorithm can result in an improved randomized algorithm which can make the expectation of the times of compare less than 3n in cases that data are uniformly distributed.

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

分 类 号：TP301.5[自动化与计算机技术—计算机系统结构]