El algoritmo de voto mayoritario de Boyer-Moore es un algoritmo para encontrar el elemento dominante en una secuencia. El elemento predominante de una secuencia de longitud n es un elemento de esta secuencia que aparece en ella más de n/2 veces. La complejidad de este algoritmo es O(n), y la memoria adicional requerida es O(1).
El algoritmo lleva el nombre de R. Boyer y Jay Moore , quienes lo publicaron en 1981. [una]
El algoritmo requiere la introducción de dos variables adicionales: la primera contendrá el elemento de la secuencia, que es el más adecuado para el papel de elemento predominante de los ya considerados, y la segunda es un contador y es inicialmente igual a cero. El algoritmo consiste en un solo paso a través de la secuencia considerada. En cada paso, se realizan las siguientes acciones: si el valor actual de la variable del contador es cero, entonces este elemento de la secuencia se escribe en la primera variable y el contador se vuelve igual a 1. Si el valor del contador es diferente de cero , luego el elemento actual de la secuencia se compara con el valor escrito en la primera variable. Si coinciden, el contador se incrementa en 1; de lo contrario, se decrementa en 1.
Pseudocódigo del algoritmo :
Después de considerar todos los elementos, la primera variable contendrá el elemento dominante de la secuencia, si existe. Sin embargo, si no existe tal elemento en la secuencia, la primera variable seguirá conteniendo algún elemento de la secuencia. Por lo tanto, si no hay certeza de que exista el elemento dominante, se debe realizar un paso adicional a través de la matriz para asegurarse de que el elemento encontrado en la matriz aparezca más de n/2 veces. Si, como resultado de la segunda pasada, resulta que el elemento no aparece más de n/2 veces, entonces la secuencia del elemento dominante no contiene. [2]