高效平均选小算法：预期时间界限

5星 · 超过95%的资源需积分: 10 113 浏览量更新于2024-09-30 收藏 675KB PDF 举报

在本篇论文中，作者讨论了"预期时间界限 for selection"这一主题，这是计算机科学中的一个重要问题，主要关注在一组包含 n 个不同数值的集合 X 中找到第 i 小的元素（1 < i < n）所需的最少比较次数。这个算法由 G. Manacher、Robert W. Floyd 和 Ronald L. Rivest 提出，他们旨在设计一个既理论上有高效性又在实践中表现良好的新选择算法。论文的核心焦点在于提供上界和下界估计，即期望的计算复杂度分析。具体来说，他们展示了选择第 i 个最小元素所需的比较次数的期望值为 n * q - min(i, n - i) + o(n)，其中 q 是一个常数。这意味着算法的时间效率与 i 的大小有关，对于中位数（i = n/2）的选择，这个公式尤其适用。论文还引入了"selection"、"computational complexity"（计算复杂性）、"medians"（中位数）以及"tournaments"（锦标赛，此处可能指数据排序竞赛）和"quantiles"（四分位数）等关键词，表明研究涵盖了这些概念在算法设计和性能评估中的应用。该论文归类于计算机科学的5.30和5.39类别，表明它与算法分析和数据结构紧密相关。介绍部分明确了研究背景，指出在实际应用中，如数据库查询、数据分析或实时系统中，找到元素排名的快速方法至关重要。作者们通过理论证明和实验验证，不仅提出了新的算法，还给出了一个接近最优的下界，这表明其算法在性能上具有显著优势，尤其是在处理大规模数据时。总结来说，这篇论文是关于优化算法设计、理论分析与实践相结合的研究，旨在提高查找数组中指定位置元素的平均效率，并且在给出的上下界分析中，显示了作者对算法复杂性和实际性能的深入理解。这对于了解和应用现代数据处理技术的工程师和研究人员来说，具有重要的参考价值。

Programming G. Manacher

Techniques Editor

Expected Time Bounds

for Selection

Robert W. Floyd and Ronald L. Rivest

Stanford University

new selection algorithm is presented which is

shown to be

very efficient on the average, both theo-

retically and practically.

The number of

comparisons

used to select the ith smallest of n numbers

n q- min(i,n--i) q- o(n).

lower bound

within 9

percent

the above formula is also derived.

Key Words and Phrases: selection, computational

complexity, medians, tournaments, quantiles

CR Categories: 5.30, 5.39

1. Introduction

In this paper we present new bounds (upper and

lower) on the expected time required for selection. The

selection problem

can be succinctly stated as follows:

given a set X of n distinct numbers and an integer i,

< i < n, determine the ith smallest element of X

with as few comparisons as possible. The ith smallest

element, denoted by i0 X, is that element which is

larger than exactly i -- 1 other elements, so that 1 0 X

is the smallest, and n 0 X the largest, element in X.

General permission to republish, but not for profit, all or part

of this material is granted provided that ACM's copyright notice

is given and that reference is made to the publication, to its date

of issue, and to the fact that reprinting privileges were granted

by permission of the Association for Computing Machinery.

This paper gives the theoretical background of Algorithm 489,

"The Algorithm

SELECT--for

finding the ith smallest of n ele-

ments," appearing on p. 173 of this issue.

This work was supported by the National Science Foundation

under grants GJ-992 and GJ-33170X. Authors' addresses: R.W.

Floyd, Stanford Computer Science Department, Stanford Uni-

versity, Stanford, CA 94305; R.L. Rivest, NE 43-807, Project MAC,

545 Technology Square, Cambridge, MA 02139.

We use the notations O(n) and o(n) in the following way:

f(n) < g(n) + O(n) means (3k > 0)(Vn)f(n) -- g(n) < kn, and

f(n) < g(n) + o(n) means lim~ ((f(n) --

g(n))/n) = O.

Let

f(i,n)

denote the expected number of com-

parisons required to select i 0 X. (We assume through-

out that all possible input orderings of the set X are

equally likely.) Since a selection algorithm must de-

termine, for every t C X, t ~ i0Xwhether t < i0X

or i0X < t, we have asatriviallowerbound

f(i,n)

> n- 1, for 1 < i < n. (1)

The best previously published selection algorithm is

FIND,

by C.A.R. Hoare [3]. Knuth [4] has determined

the average number of comparisons used by

FIND,

thus proving that

f(i,n) <

2((n Jr- 1)H~ -- (n -k- 3 --

i)H,~_i+l

(2)

-- (i -k- 2)Hi q- n -q- 3),

where

H,, = ~ j-1. (3)

l<j<n

This yields as special cases I

f(l,n) < 2n -4-

o(n),

(4)

and

f( [-n/2~ ,n) <_

211(1 + ln(2)) -4- o(n)

< 3.39/7 -k-

o(n).

(5)

No bounds better than (1) or (2) have previously been

published.

In Section 2 we present our new selection algorithm,

SELECT,

and derive by an analysis of its efficiency the

upper bound

f(i,n) < n + min(i,n -- i) + O(n '~

ln~'(n)). (6)

A small modification to

SELECT'is

then made, yielding

the slightly improved bound

f(i,n). <_ n +

min

(i,n

- i) + O(n½). (7)

An implementation of

SELECT

is given in Section 3

with timing results for both

SELECT

and

FIND.

The authors believe that

SELECT

is asymptotically

optimal in the sense that the function

sup f(

L~(n

-- 1)__1 + 1, 11)

F(~)

lim

(~Tef

.... n (8)

0<~<1

is bounded below by the analogue of the right-hand

side of (7), so that

F(a) >__ 1 -k min (¢,, 1 -- a), for 0_< ~_< l. (9)

A lower bound just a little better than 1 q- .75 min

(a, I -- a) is derived in Section 4, within 9 percent of

our conjecture and the performance of

SELECT.

165

Communications March 1975

of Volume 18

the ACM Number 3

下载后可阅读完整内容，剩余7页未读，立即下载

mostovoi1234

粉丝: 31
资源: 239

高效平均选小算法：预期时间界限

Blum、Floyd、Pratt、Rivest、Tarjan__Time bounds for selection.pdf

Time Bounds For Selection

iOS json解析出错的几种情况总结

cpp-JSONC的JSON解析器

解决 VSCode 编辑 vue 项目报错 Expected indentation of 2 spaces but found 4

spring 异步编程样例

带有 python 3 和 opencv 4.1 的 Docker 映像.zip

原生js鼠标滑过文字淡入淡出效果.zip

1-中国各省、市、区、县距离港口和海岸线的距离计算代码+计算结果-社科数据.zip

为 Spring Web 应用提供 OAuth1 (a) 和 OAuth2 功能支持.zip

最新资源