10月4日论文推荐（附下载地址）

论文名：

Time Bounds for Selection

会议/年份： JOURNAL OF COMPUTER AND SYSTEM SCIENCES 1973

作者：

MANUEL BLUM, ROBERT W. FLOYD, VAUGHAN PRATT, RONALD L. RIVEST, AND ROBERT E. TARJAN

推荐理由：

对于n个数据中，寻找第k大数,在基于比较的算法中，该文介绍一种最坏时间复杂度为线性的算法，并对该算法的系数进行讨论优化。是目前了解到的该问题的最优解。感觉文章有2处看点:1.相比O(nlogn)的算法，O(n)算法的优化思路；2. 对线性算法系数优化线性算法系数的讨论过程n。

Abstract

In this paper we present a new selection algorithm, PICK, and derive by an analysis of its efficiency the (surprising) result that the cost of selection is at most a linear function of the number of input items. In addition, we prove a new lower bound for the cost of selection.

The selection problem is perhaps best exemplified by the computation of medians. In general, we may wish to select the i-th smallest of a set of n distinct numbers, or the element ranking closest to a given percentile level.

论文下载链接：

https://www.aminer.cn/archive/time-bounds-for-selection/53e99adcb7602d970235f275