摘要
顺序统计问题是算法设计与分析中的一个典型的问题,即从n个元素中选出第k个最小元素。文章采用分治算法解决顺序统计问题,给出了通用算法,并对算法的复杂性进行了分析和讨论。对于子序列长度大于5的情形,该算法的最坏情形的时间复杂性为O(n)。
The order statistics problem,which is to find the kth smallest element in a sequence of n numbers in arbitrary order,is a typical problem in algorithm design and analysis. The order statistics problem is solved by dividing and conquering algorithm. The general algorithm is given, and the complexity of this algorithm is analyzed and discussed. If the length of subsequence is larger than 5, on the worst-case the running time of this algorithm is O(n).
出处
《微机发展》
2003年第7期80-81,共2页
Microcomputer Development
