会议/年份： 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./archive/time-bounds-for-selection/53e99adcb7602d970235f275 |
|
|
