Algoritmul votului majoritar Boyer-Moore este un algoritm pentru găsirea elementului dominant într-o secvență. Elementul predominant al unei secvențe de lungime n este un element al acestei secvențe care apare în ea de mai mult de n/2 ori. Complexitatea acestui algoritm este O(n), iar memoria suplimentară necesară este O(1).
Algoritmul este numit după R. Boyer și Jay Moore , care l-au publicat în 1981. [unu]
Algoritmul necesită introducerea a două variabile suplimentare: prima va conține elementul secvenței, care este cel mai potrivit pentru rolul elementului predominant dintre cele deja luate în considerare, iar a doua este un numărător și este inițial egală cu zero. Algoritmul constă dintr-o singură trecere prin secvența considerată. La fiecare pas, se efectuează următoarele acțiuni: dacă valoarea curentă a variabilei contorului este zero, atunci acest element al secvenței este scris în prima variabilă, iar contorul devine egal cu 1. Dacă valoarea contorului este diferită de zero , apoi elementul curent al secvenței este comparat cu valoarea scrisă la prima variabilă. Dacă se potrivesc, atunci contorul este incrementat cu 1, în caz contrar este decrementat cu 1.
Pseudocod algoritm :
După luarea în considerare a tuturor elementelor, prima variabilă va conține elementul dominant al secvenței, dacă există unul. Totuși, dacă nu există un astfel de element în secvență, atunci prima variabilă va conține în continuare un element al secvenței. Prin urmare, dacă nu există nicio certitudine că elementul dominant există, atunci ar trebui efectuată o trecere suplimentară prin matrice pentru a vă asigura că elementul găsit în matrice apare de mai mult de n/2 ori. Dacă, în urma celei de-a doua treceri, se dovedește că elementul apare de cel mult n/2 ori, atunci secvența elementului dominant nu conține. [2]