Boyer–Moore majoritetsröstalgoritm
Boyer –Moores majoritetsröstalgoritm är en algoritm för att hitta majoriteten av en sekvens av element med hjälp av linjär tid och konstant rum. Den är uppkallad efter Robert S. Boyer och J Strother Moore , som publicerade den 1981, och är ett prototypiskt exempel på en strömningsalgoritm .
I sin enklaste form hittar algoritmen ett majoritetselement, om det finns ett: det vill säga ett element som förekommer upprepade gånger för mer än hälften av elementen i inmatningen. En version av algoritmen som gör en andra passage genom data kan användas för att verifiera att elementet som finns i det första passet verkligen är en majoritet.
Om ett andra pass inte utförs och det inte finns någon majoritet kommer algoritmen inte att upptäcka att ingen majoritet existerar. Om det inte finns någon strikt majoritet kan det returnerade elementet vara godtyckligt; Det är inte garanterat att det är det element som förekommer oftast ( sekvensens läge ). Det är inte möjligt för en strömningsalgoritm att hitta det vanligaste elementet i mindre än linjärt utrymme, för sekvenser vars antal repetitioner kan vara litet.
Beskrivning
Algoritmen upprätthåller i sina lokala variabler ett sekvenselement och en räknare, med räknaren initialt noll. Den bearbetar sedan elementen i sekvensen, en i taget. Vid bearbetning av ett element x , om räknaren är noll, lagrar algoritmen x som sitt ihågkomna sekvenselement och ställer räknaren till ett. Annars jämför den x med det lagrade elementet och antingen ökar räknaren (om de är lika) eller minskar räknaren (annars). I slutet av denna process, om sekvensen har en majoritet, kommer det att vara det element som lagras av algoritmen. Detta kan uttryckas i pseudokod som följande steg:
- Initiera ett element m och en räknare i med i = 0
- För varje element x i inmatningssekvensen:
- Om i = 0 , tilldela då m = x och i = 1
- annars om m = x , tilldela i = i + 1
- annars tilldela i = i − 1
- Återgå m
Även när inmatningssekvensen inte har någon majoritet kommer algoritmen att rapportera ett av sekvenselementen som dess resultat. Det är dock möjligt att utföra en andra pass över samma inmatningssekvens för att räkna antalet gånger det rapporterade elementet inträffar och avgöra om det faktiskt är en majoritet. Denna andra passage behövs, eftersom det inte är möjligt för en sublinjär rymdalgoritm att avgöra om det finns ett majoritetselement i en enda passage genom ingången.
Analys
Mängden minne som algoritmen behöver är utrymmet för ett element och en räknare. I den direktåtkomstmodell av datorer som vanligtvis används för analys av algoritmer kan vart och ett av dessa värden lagras i ett maskinord och det totala utrymmet som behövs är O (1) . Om ett arrayindex behövs för att hålla reda på algoritmens position i inmatningssekvensen, ändrar det inte den totala konstanta utrymmesgränsen. Algoritmens bitkomplexitet (utrymmet den skulle behöva, till exempel på en Turing-maskin ) är högre, summan av de binära logaritmerna för ingångslängden och storleken på universum från vilket elementen hämtas. Både random access-modellen och bitkomplexitetsanalyserna räknar bara algoritmens arbetsminne och inte lagringen för själva inmatningssekvensen.
På liknande sätt, på en direktåtkomstmaskin, tar algoritmen tiden O ( n ) (linjär tid) på en ingångssekvens av n poster, eftersom den endast utför ett konstant antal operationer per ingångspost. Algoritmen kan också implementeras på en Turing-maskin i tidlinjär i ingångslängden ( n gånger antalet bitar per ingångspost).
Rätthet
Antag att vi har en sekvens av storlek N som har ett majoritetselement m . Det kan visas som negation att algoritmen inte kan mata ut ett icke-majoritetselement.
Algoritmen väljer det första elementet i sekvensen som majoritetskandidat c och initierar en räknare för den kandidaten med värde 1. Om kandidaten inte är majoritetselementet måste räknaren nå noll eftersom det finns fler element i sekvensen som är inte lika med kandidaten. När räknaren når noll efter K < N iterationer, då konsumerade vi exakt K / 2 element med kandidatvärdet (K måste vara jämnt). Oavsett om kandidaten är lika med majoritetselementet m eller inte, lämnas vi med en följd av längden N - K där m fortfarande är majoritetselementet.
Se även
- Element distinctness problem , problemet med att testa om en samling av element har några upprepade element
- Majoritetsfunktion , majoriteten av en samling booleska värden
- Majoritetsproblem (cellulär automat) , problemet med att hitta ett majoritetselement i den cellulära automatens beräkningsmodell
- Misra–Gries heavy hitters algoritm och Misra–Gries sammanfattning , den naturliga generaliseringen av Boyer Moore till att lagra mer än ett föremål.