The average-case complexity of determining the majority

被引：32

作者：

Alonso, L

Reingold, EM

Schott, R

机构：

[1] ENS,F-75005 PARIS,FRANCE

[2] UNIV ILLINOIS,DEPT COMP SCI,URBANA,IL 61801

来源：

SIAM JOURNAL ON COMPUTING | 1997年 / 26卷 / 01期

关键词：

algorithm analysis; decision trees; lower bounds; average case;

D O I：

10.1137/S0097539794275914

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

Given a set of n elements each of which is either red or blue, it is known that in the worst case n - v(n) pairwise equal/not equal color comparisons are necessary and sufficient to determine the majority color, where v(n) is the number of 1-bits in the binary representation of n. We prove that 2n/3 - root 8n/9 pi + O(log n) such comparisons are necessary and sufficient in the average case.

引用

页码：1 / 14

页数：14

共 11 条

[1]

Alexanderson G. L., 1985, WL PUTNAM MATH COMPE

[2] DETERMINING THE MAJORITY [J].

ALONSO, L ;

REINGOLD, EM ;

SCHOTT, R .

INFORMATION PROCESSING LETTERS, 1993, 47 (05) :253-255

[3]

[Anonymous], 1990, MATH ANAL ALGORITHMS

[4]

Feller W., 1968, INTRO PROBABILITY TH

[5] COIN-WEIGHING PROBLEMS [J].

GUY, RK ;

NOWAKOWSKI, RJ .

AMERICAN MATHEMATICAL MONTHLY, 1995, 102 (02) :164-167

[6]

HAKIMI SL, 1984, J ALGORITHM, V5, P526, DOI 10.1016/0196-6774(84)90005-1

[7]

HILLMAN AP, 1975, WL PUTNAM MATH COMPE, V82, P905

[8]

REINGOLD EM, 1977, COMBINATORIAL ALGORI

[9] ON COMPUTING MAJORITY BY COMPARISONS [J].

SAKS, ME ;

WERMAN, M .

COMBINATORICA, 1991, 11 (04) :383-387

[10] A PARALLEL FAULT IDENTIFICATION ALGORITHM [J].

SCHMEICHEL, E ;

HAKIMI, SL ;

OTSUKA, M ;

SULLIVAN, G .

JOURNAL OF ALGORITHMS, 1990, 11 (02) :231-241

← 1 2 →