Average-Case Analysis of Some Plurality Algorithms

作者：Alonso Laurent^*; Reingold Edward M

来源：ACM Transactions on Algorithms, 2009, 5(2): 17.

DOI：10.1145/1497290.1497293

• Algorithm analysis
• majority problem
• plurality problem

Given a set of n elements, each of which is colored one of c colors, we must determine an element of the plurality (most frequently occurring) color by pairwise equal/unequal color comparisons of elements. We focus on the expected number of color comparisons when the c(n) colorings are equally probable. We analyze an obvious algorithm, showing that its expected performance is c(2) 1c 2/2cn-O(c(2)), with variance Theta(c(2)n). We present and analyze an algorithm for the case c = 3 colors whose average complexity on the 3(n) equally probable inputs is 7083/5425n O(root n) = 1.3056....n O(root n), substantially better than the expected complexity 5/3n O(1) = 1.6666...n O(1) of the obvious algorithm. We describe a similar algorithm for c = 4 colors whose average complexity on the 4(n) equally probable inputs is 761311/402850n O(log n) = 1.8898...n O(log n), substantially better than the expected complexity 9/4n O(1) = 2.25n O(1) of the obvious algorithm.

• 出版日期2009-3
• 单位INRIA