Selecting the median

被引：44

作者：

Dor, D ^{[1
]}

Zwick, U ^{[1
]}

机构：

[1] Tel Aviv Univ, Raymond & Beverly Sackler Fac Exact Sci, Sch Math Sci, Dept Comp Sci, IL-69978 Tel Aviv, Israel

来源：

SIAM JOURNAL ON COMPUTING | 1999年 / 28卷 / 05期

关键词：

median selection; comparison algorithms; concrete complexity;

D O I：

10.1137/S0097539795288611

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

Improving a long-standing result of Schonhage, Paterson, and Pippenger [J. Comput. System Sci., 13 (1976), pp. 184-199] we show that the median of a set containing n elements can always be found using at most c . n comparisons, where c < 2.95.

引用

页码：1722 / 1758

页数：37

共 26 条

[1] SELECTING THE TOP 3 ELEMENTS [J].

AIGNER, M .

DISCRETE APPLIED MATHEMATICS, 1982, 4 (04) :247-267

[2]

Bent S.W., 1985, P 17 ANN ACM S THEOR, P213

[3]

Blum M., 1973, Journal of Computer and System Sciences, V7, P448, DOI 10.1016/S0022-0000(73)80033-9

[4] AVERAGE CASE SELECTION [J].

CUNTO, W ;

MUNRO, JI .

JOURNAL OF THE ACM, 1989, 36 (02) :270-279

[5] Finding the alpha n-th largest element [J].

Dor, D ;

Zwick, U .

COMBINATORICA, 1996, 16 (01) :41-58

[6]

DOR D, 1995, PROCEEDINGS OF THE SIXTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, P28

[7] Median selection requires (2+epsilon)n comparisons [J].

Dor, D ;

Zwick, U .

37TH ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, PROCEEDINGS, 1996, :125-134

[8]

DOR D, 1995, THESIS TEL AVIV U TE

[9] ERRATA TO SELECTING THE TOP 3 ELEMENTS BY AIGNER,M. - A RESULT OF A COMPUTER-ASSISTED PROOF SEARCH [J].

EUSTERBROCK, J .

DISCRETE APPLIED MATHEMATICS, 1993, 41 (02) :131-137

[10] EXPECTED TIME BOUNDS FOR SELECTION [J].

FLOYD, RW ;

RIVEST, RL .

COMMUNICATIONS OF THE ACM, 1975, 18 (03) :165-172

← 1 2 3 →