多数投票算法

博耶-摩尔多数投票算法（英语：Boyer–Moore majority vote algorithm）,中文常作多数投票算法、摩尔投票算法等，是一种用来寻找一组元素中占多数元素的常数空间级时间复杂度算法。这一算法由罗伯特·S·博耶（英语：Robert S. Boyer）和J·斯特罗瑟·摩尔（英语：J Strother Moore）在1981年发表^[1]，也是处理数据流（英语：streaming algorithm）的一种典型算法。

x轴为计数器中存储的元素，而下方y轴为输入的元素序列。遇到相同元素或者计数器中没有元素，计数器加入重复元素，如果遇到不同元素计数器消除一个元素。

这一算法应用的问题原型是在集合中寻找可能存在的多数元素，这一元素在输入的序列重复出现并占到了序列元素的一半以上；在第一遍遍历之后应该再进行一个遍历以统计第一次算法遍历的结果出现次数，确定其是否为众数；如果一个序列中没有占到多数的元素，那么第一次的结果就可能是无效的随机元素。对于数据流而言，则不太可能在亚线性空间复杂度的情况下中就寻找到出现频率最高的元素；而对于序列，其元素的重复次数也有可能很低。^[2]

算法

算法可以用伪代码如下表示：

初始化元素 $m$ 并给计数器 $i$ 赋初值 $i = 0$
对于输入队列中每一个元素 $x$ ：
- 若 $i = 0$ , 那么 $m = x$ and $i = 1$
- 否则若 $m = x$ , 那么 $i = i + 1$
- 否则 $i = i - 1$
返回 $m$

即便输入序列没有多数元素，这一算法也会返回一个序列元素。然而如果能够进行第二轮遍历，检验返回元素的出现次数，就能判断返回元素是否为多数元素。因此算法需要两次遍历，亚线性空间算法无法通过一次遍历就得出输入中是否存在多数元素。^[3]

参见

元素唯一性问题，判断序列中该元素唯一
多数函数（英语：Majority function），返回多数元素的布尔类型集合
多数问题 (元胞自动机)（英语：Majority problem (cellular automaton)），在细胞自动机计算模型中寻找多数元素

参考资料

^ Boyer, R. S.; Moore, J S., MJRTY - A Fast Majority Vote Algorithm, Boyer, R. S. (编), Automated Reasoning: Essays in Honor of Woody Bledsoe, Automated Reasoning Series, Dordrecht, The Netherlands: Kluwer Academic Publishers: 105–117, 1991, doi:10.1007/978-94-011-3488-0_5 . Originally published as a technical report in 1981.
^ Trevisan, Luca; Williams, Ryan, Notes on streaming algorithms (PDF), CS154: Automata and Complexity (Stanford University), January 26, 2012 [2020-06-03], （原始内容存档 (PDF)于2017-08-29） .
^ Cormode, Graham; Hadjieleftheriou, Marios, Finding the frequent items in streams of data, ACM通讯, October 2009, 52 (10): 97, doi:10.1145/1562764.1562789, no algorithm can correctly distinguish the cases when an item is just above or just below the threshold in a single pass without using a large amount of space .

[bm-1] Boyer, R. S.; Moore, J S., MJRTY - A Fast Majority Vote Algorithm, Boyer, R. S. (编), Automated Reasoning: Essays in Honor of Woody Bledsoe, Automated Reasoning Series, Dordrecht, The Netherlands: Kluwer Academic Publishers: 105–117, 1991, doi:10.1007/978-94-011-3488-0_5 . Originally published as a technical report in 1981.

[cs154-2] Trevisan, Luca; Williams, Ryan, Notes on streaming algorithms (PDF), CS154: Automata and Complexity (Stanford University), January 26, 2012 [2020-06-03], （原始内容存档 (PDF)于2017-08-29） .

[3] Cormode, Graham; Hadjieleftheriou, Marios, Finding the frequent items in streams of data, ACM通讯, October 2009, 52 (10): 97, doi:10.1145/1562764.1562789, no algorithm can correctly distinguish the cases when an item is just above or just below the threshold in a single pass without using a large amount of space .

[1]

[2]

[3]