h3. Soluţie O(n + k) probabilistică

Putem aborda probabilistic. Astfel dacă alegem un număr aleator şi există o celebritate, avem probabilitatea $0.5$ să nu îl nimerim. Dacă alegem $k$ numere aleatoare din şirul respectiv, atunci avem probabilitatea <tex> (\frac{1}{2})^k </tex> să nu îl nimerim. Astfel algoritmul nostru va fi să luăm $k$ numere aleatoare, iar apoi să numărăm de câte ori apare fiecare din aceste $k$ numere în şirul nostru. Dacă folosim o structură ce mapează $<chei, valori>$ atunci algoritmul va avea complexitate $O(n + k)$ şi probabilitate de reuşită $P = 1 - <tex> (\frac{1}{2})^k </tex>$. În practică o valoare de $10$ pentru $k$ ne dă o probabilitate de reuşită de $0.999$. Să vedem mai departe codul:

Putem aborda probabilistic. Astfel dacă alegem un număr aleator şi există o celebritate, avem probabilitatea $0.5$ să nu îl nimerim. Dacă alegem $k$ numere aleatoare din şirul respectiv, atunci avem probabilitatea <tex> (\frac{1}{2})^k </tex> să nu îl nimerim. Astfel algoritmul nostru va fi să luăm $k$ numere aleatoare, iar apoi să numărăm de câte ori apare fiecare din aceste $k$ numere în şirul nostru. Dacă folosim o structură ce mapează $<chei, valori>$ atunci algoritmul va avea complexitate $O(n + k)$ şi probabilitate de reuşită <tex> P = 1 - (\frac{1}{2})^k </tex>. În practică o valoare de $10$ pentru $k$ ne dă o probabilitate de reuşită de $0.999$. Să vedem mai departe codul:

== code(cpp) |
int probabilisticMajority(int n, int[] a) {

}
==

Bibliografie:

h2. Bibliografie
 

# T.H.Cormen, C. E. Leiserson, R. R. Rivest, Introducere în algoritmi, ed. Agora 2000
# R. S. Boyer, J. S. Moore A Fast Majority Vote Algorithm