El algoritmo de votación mayoritaria de Boyer-Moore es un algoritmo para encontrar la mayoría de una secuencia de elementos utilizando tiempo lineal y un número constante de palabras de memoria. Recibe su nombre en honor a Robert S. Boyer y J Strother Moore , quienes lo publicaron en 1981, [1] y es un ejemplo prototípico de un algoritmo de transmisión .
En su forma más simple, el algoritmo encuentra un elemento mayoritario, si lo hay: es decir, un elemento que aparece repetidamente en más de la mitad de los elementos de la entrada. Se puede utilizar una versión del algoritmo que realiza un segundo paso por los datos para verificar que el elemento encontrado en el primer paso es realmente mayoritario. [1]
Si no se realiza un segundo paso y no hay mayoría, el algoritmo no detectará que no existe mayoría. En el caso de que no exista una mayoría estricta, el elemento devuelto puede ser arbitrario; no se garantiza que sea el elemento que aparece con mayor frecuencia (la moda de la secuencia). No es posible que un algoritmo de streaming encuentre el elemento más frecuente en un espacio menor que el lineal, para secuencias cuyo número de repeticiones puede ser pequeño. [2]
El algoritmo mantiene en sus variables locales un elemento de secuencia y un contador, con el contador inicialmente a cero. Luego procesa los elementos de la secuencia, uno a la vez. Al procesar un elemento x , si el contador es cero, el algoritmo almacena x como su elemento de secuencia recordado y establece el contador en uno. De lo contrario, compara x con el elemento almacenado y aumenta el contador (si son iguales) o lo disminuye (en caso contrario). Al final de este proceso, si la secuencia tiene una mayoría, será el elemento almacenado por el algoritmo. Esto se puede expresar en pseudocódigo como los siguientes pasos:
Incluso cuando la secuencia de entrada no tiene mayoría, el algoritmo informará uno de los elementos de la secuencia como su resultado. Sin embargo, es posible realizar una segunda pasada sobre la misma secuencia de entrada para contar la cantidad de veces que aparece el elemento informado y determinar si realmente es una mayoría. Esta segunda pasada es necesaria, ya que no es posible que un algoritmo de espacio sublineal determine si existe un elemento mayoritario en una sola pasada a través de la entrada. [3]
La cantidad de memoria que necesita el algoritmo es el espacio para un elemento y un contador. En el modelo de acceso aleatorio de computación que se usa habitualmente para el análisis de algoritmos , cada uno de estos valores se puede almacenar en una palabra de máquina y el espacio total necesario es O (1) . Si se necesita un índice de matriz para realizar un seguimiento de la posición del algoritmo en la secuencia de entrada, no cambia el límite de espacio constante general. La complejidad de bits del algoritmo (el espacio que necesitaría, por ejemplo, en una máquina de Turing ) es mayor que la suma de los logaritmos binarios de la longitud de entrada y el tamaño del universo del que se extraen los elementos. [2] Tanto el modelo de acceso aleatorio como los análisis de complejidad de bits solo cuentan el almacenamiento de trabajo del algoritmo, y no el almacenamiento para la secuencia de entrada en sí.
De manera similar, en una máquina de acceso aleatorio el algoritmo tarda un tiempo O ( n ) (tiempo lineal) en una secuencia de entrada de n elementos, porque realiza solo un número constante de operaciones por elemento de entrada. El algoritmo también se puede implementar en una máquina de Turing en un tiempo lineal en la longitud de entrada ( n veces el número de bits por elemento de entrada). [4]
Supongamos que la entrada contiene un elemento mayoritario x , cuyo número de copias es más de la mitad de la longitud de entrada. Entonces el algoritmo debería devolver x como su valor final m . Boyer y Moore prueban la siguiente afirmación más fuerte: Para los valores finales m y c del algoritmo, en una secuencia de longitud n , siempre es posible particionar los valores de entrada en c copias de m y ( n − c )/2 pares de elementos desiguales. De esto se deduce que ningún elemento x ≠ m puede tener una mayoría, porque x puede tener como máximo la mitad de los elementos en los pares desiguales y ninguna de las c copias restantes de m . Por lo tanto, si hay un elemento mayoritario, solo puede ser m . [1]
Para demostrar la existencia de esta partición, Boyer y Moore proceden por inducción sobre la longitud de la secuencia de entrada. En cada paso, utilizan la hipótesis de inducción para encontrar una partición del mismo tipo para la subsecuencia de la entrada con su último elemento eliminado, con su valor de m . Si el valor de entrada final también es igual a m , se agrega al conjunto de c copias de m . Si es diferente de m , y c era positivo, entonces una de las c copias de m se elimina de este conjunto de copias y se empareja con el valor final. Y si c era cero, entonces el valor final se puede agregar al conjunto (previamente vacío) de copias de m , incluso si este paso hace que m cambie. Por lo tanto, en todos los casos, la partición descrita por Boyer y Moore continúa existiendo. [1]
ningún algoritmo puede distinguir correctamente los casos en los que un elemento está justo por encima o justo por debajo del umbral en una sola pasada sin utilizar una gran cantidad de espacio.