多数投票算法
博耶-摩尔多数投票算法（英語：Boyer–Moore majority vote algorithm）,中文常作多数投票算法、摩尔投票算法等，是一种用来寻找一组元素中占多数元素的常数空间级时间复杂度算法。这一算法由罗伯特·S·博耶和J·斯特罗瑟·摩尔在1981年发表[1]，也是处理数据流的一种典型算法。
这一算法应用的问题原型是在集合中寻找可能存在的多数元素，这一元素在输入的序列重复出现并占到了序列元素的一半以上；在第一遍遍历之后应该再进行一个遍历以统计第一次算法遍历的结果出现次数，确定其是否为众数；如果一个序列中没有占到多数的元素，那么第一次的结果就可能是无效的随机元素。对于数据流而言，则不太可能在亚线性空间复杂度的情况下中就寻找到出现频率最高的元素；而对于序列，其元素的重复次数也有可能很低。[2]
算法 编辑
该算法在其局部变量中存储一个数组元素和一个计数器，计数器初始化为 0。然后对数组进行遍历操作，在遍历到元素 x 的时候：如果计数器为 0，则算法将 x 存储到数组元素变量，并将计数器设置为 1。 否则，它将 x 与存储的元素进行比较，然后递增计数器（如果它们相等）或递减计数器（不相等）。 在此过程结束时，如果数组中存在占多数的元素，则它将是存储的数组元素变量的值。
算法可以用伪代码如下表示：
- 初始化元素m并给计数器i赋初值i = 0
- 对于输入队列中每一个元素x：
- 若i = 0, 那么 m = x and i = 1
- 否则若m = x, 那么 i = i + 1
- 否则 i = i − 1
- 返回 m
即便输入序列没有多数元素，这一算法也会返回一个序列元素。然而如果能够进行第二轮遍历，检验返回元素的出现次数，就能判断返回元素是否为多数元素。因此算法需要两次遍历，亚线性空间算法无法通过一次遍历就得出输入中是否存在多数元素。[3]
参见 编辑
- 元素唯一性问题，判断序列中该元素唯一
- 多数函数，返回多数元素的布尔类型集合
- 多数问题 (元胞自动机)，在細胞自動機计算模型中寻找多数元素
参考资料 编辑
- ^ 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
.