Bojer-Murov algoritam većinskog glasa

Bojer-Murov algoritam preovlađujućeg elementa u linearnom vremenu[O(n)] i konstantnoj prostornoj složenosti [O(1)]. Problem preovlađujućeg elementa služi da se utvrdi da li u nekoj unapred zadatoj nisci postoji neki element koji je većinski, i ako postoji algoritam nam daje konkretan element. Matematički, za zadatu konačnu nisku (dužine n), cilj je pronaći element koji se pojavljuje više od [ n/2 ] puta.

Opis

Algoritam se izvršava u dva koraka:

1. Eleminisati sve elemente osim jednog.

Iterirajući kroz nisku, održavamo trenutnog kandidata i brojač (brojač je inicijalno 0). Prolaskom kroz niz u svakom koraku uvećavamo vrednost brojača (Ukoliko naiđemo na element koga smo proglasili za kandaidata) inače smanjujemo brojač. U slučaju da je brojač 0, naredni element proglašavamo za kandidata i nastavljamo pretragu.

2. Provera da li je preostali kandidat zaista većinski.

Nakon što smo izdvojili potencijalnog kandidata u koraku 1, prolazimo kroz nisku i prebrojavamo broj pojavljivanja našeg kandidata. Ukoliko je broj pojavljivanja našeg kandidata veći od polovine dužine niske, tada je naš kandidat zaista većinski element. Inače naša niska nema većinski element.

Implementacije u C-u

Algoritam Preovladjuje (x,n):
ulaz: x, n /* niz pozitivnih brojeva x, dimenzije n*/
izlaz: preovlada /* preovladjujuci alaement (ako postoji) ili -1 */
C=x[0];
M=1;
for(i=1; i < n; i++)
 if (M==0)
 {C=x[i]; M=1;}
 else
 if (x[i]==C) M++; else M--;
if (M==0) preovlada=-1; /*nema preovladjujuceg elementa*/
else brojac=0;
for (i=0; i < n; i++)
 if (x[i]==C) brojac++;
if (brojac > n/2) preovlada=C; else preovlada=-1; 

Algoritam Preovladjuje (x,n):
Ulaz x, n /* niz brojeva x, dimenzije n*/
Izlaz /* preovladjujuci element (ako postoji) ili -1 */
{
  C=x[0];
  M=1;
  for(i=1; i<n; i++){
    if (M==0) {
      C=x[i];
      M=1;
    }
    else {
      if (x[i]==C) M++;
      else M--;
    }
  }
  if (M==0)
    return -1; /*nema preovladjujuceg elementa*/
  else
    brojac=0;
  for (i=0; i < n; i++)
    if (x[i]==C)
      brojac++;
  if (brojac > n/2)
    return C;
  else
    return -1;
}

Implementacija u Javi

import java.util.*;
public class MajorityVote {
    public int majorityElement(int[] num) {
        int n = num.length;
        int candidate = num[0], counter = 0;
        for (int i : num) {
            if (counter == 0) {
                candidate = i;
                counter = 1;
            } else {
                if (i == candidate) {
                    counter++;
                } else {
                    counter--;
                }
            }
        }

        counter = 0;
        for (int i : num) {
            if (i == candidate) counter++;
        }
        if (counter < (n + 1) / 2) return -1;
        return candidate;

    }
    public static void main(String[] args) {
        MajorityVote s = new MajorityVote();
        System.out.format("%d\n", s.majorityElement(new int[] {1, 2, 3}));
        System.out.format("%d\n", s.majorityElement(new int[] {2, 2, 3}));
    }
}

Spoljašnje veze

• [1]
• Primer izvršavanja programa
• [2] Архивирано на сајту Wayback Machine (31. децембар 2016)