Boyer-Moores majoritetsröstalgoritm är en algoritm för att hitta det dominerande elementet i en sekvens. Det dominerande elementet i en sekvens med längden n är ett element i denna sekvens som förekommer i den mer än n/2 gånger. Komplexiteten för denna algoritm är O(n), och det extra minnet som krävs är O(1).
Algoritmen är uppkallad efter R. Boyer och Jay Moore , som publicerade den 1981. [ett]
Algoritmen kräver införandet av två ytterligare variabler: den första kommer att innehålla elementet i sekvensen, som är det mest lämpliga för rollen som det dominerande elementet från de som redan har beaktats, och den andra är en räknare och är initialt lika med noll. Algoritmen består av en enda passage genom den betraktade sekvensen. Vid varje steg utförs följande åtgärder: om det aktuella värdet på räknarvariabeln är noll, skrivs detta element i sekvensen till den första variabeln och räknaren blir lika med 1. Om räknarvärdet skiljer sig från noll , sedan jämförs det aktuella elementet i sekvensen med värdet som skrivits till den första variabeln. Om de matchar, så ökas räknaren med 1, annars minskas den med 1.
Algoritm pseudokod :
Efter att ha övervägt alla element kommer den första variabeln att innehålla det dominerande elementet i sekvensen, om en sådan finns. Men om det inte finns något sådant element i sekvensen, kommer den första variabeln fortfarande att innehålla något element i sekvensen. Därför, om det inte finns någon säkerhet att det dominerande elementet existerar, bör en ytterligare passage genom arrayen utföras för att säkerställa att det hittade elementet i arrayen inträffar mer än n/2 gånger. Om det, som ett resultat av det andra passet, visar sig att elementet inte förekommer mer än n/2 gånger, innehåller sekvensen av det dominerande elementet inte. [2]