ON COMPUTING MAJORITY BY COMPARISONS

被引：47

作者：

SAKS, ME

WERMAN, M

机构：

[1] RUTGERS STATE UNIV,DEPT MATH,NEW BRUNSWICK,NJ 08903

[2] RUTGERS STATE UNIV,RUTCOR,NEW BRUNSWICK,NJ 08903

[3] BELL COMMUN RES INC,MORRISTOWN,NJ 07960

[4] UNIV MINNESOTA,DEPT MATH & APPLICAT,MINNEAPOLIS,MN 55455

来源：

COMBINATORICA | 1991年 / 11卷 / 04期

关键词：

AMS subject classification (1991): 68P10; 68R05;

D O I：

10.1007/BF01275672

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

The elements of a finite set X (of odd cardinality n) are divided into two (as yet unknown) classes and a member of the larger class is to be identified. The basic operation is to test whether two objects are in the same class. We show that n - B(n) comparisons are necessary and sufficient in worst case, where B(n) is the number of 1's in the binary expansion of n.

引用

页码：383 / 387

页数：5