Boyer-Moores flertalsafstemningsalgoritme er en algoritme til at finde det dominerende element i en sekvens. Det overvejende element i en sekvens af længden n er et element i denne sekvens, der forekommer i den mere end n/2 gange. Kompleksiteten af denne algoritme er O(n), og den nødvendige ekstra hukommelse er O(1).
Algoritmen er opkaldt efter R. Boyer og Jay Moore , som udgav den i 1981. [en]
Algoritmen kræver introduktion af to yderligere variable: den første vil indeholde elementet i sekvensen, som er det mest egnede til rollen som det dominerende element fra dem, der allerede er overvejet, og den anden er en tæller og er oprindeligt lig med nul. Algoritmen består af en enkelt passage gennem den betragtede sekvens. Ved hvert trin udføres følgende handlinger: hvis den aktuelle værdi af tællervariablen er nul, skrives dette element i sekvensen til den første variabel, og tælleren bliver lig med 1. Hvis tællerværdien er forskellig fra nul , så sammenlignes det aktuelle element i sekvensen med værdien skrevet til den første variabel. Hvis de matcher, øges tælleren med 1, ellers reduceres den med 1.
Algoritme pseudokode :
Efter at have overvejet alle elementerne, vil den første variabel indeholde det dominerende element i sekvensen, hvis et sådant findes. Men hvis der ikke er et sådant element i sekvensen, vil den første variabel stadig indeholde et eller andet element i sekvensen. Derfor, hvis der ikke er sikkerhed for, at det dominerende element eksisterer, skal der udføres en ekstra passage gennem arrayet for at sikre, at det fundne element i arrayet forekommer mere end n/2 gange. Hvis det, som et resultat af den anden passage, viser sig, at elementet ikke forekommer mere end n/2 gange, så indeholder sekvensen af det dominerende element ikke. [2]