Algoritmo de votación de tiempo lineal. No lo entiendo

Question

Mientras estaba leyendo esto (Find the most common entry in an array), se sugirió Boyer and Moore's Linear Time Voting Algorithm.

Si sigue el enlace al sitio, hay una explicación paso a paso de cómo funciona el algoritmo. Para la secuencia dada, AAACCBBCCCBCC presenta la solución correcta.

Cuando nos movemos hacia adelante el puntero sobre un elemento e:

• Si el contador es 0, nos fijamos el actual candidato a e y establecer el contador a 1. Si
• el contador no es 0, incrementamos o disminuimos el contador según si e es el candidato actual .

Cuando hemos terminado, la corriente candidato es el elemento de la mayoría, si hay una mayoría.

Si utilizo este algoritmo en un pedazo de papel con AAACCBB como entrada, el candidato sugerido se convertiría en B lo que es obviamente erróneo.

Tal como lo veo, hay dos posibilidades

1. Los autores nunca han probado su algoritmo en cualquier otra cosa que AAACCBBCCCBCC, son completamente incompetente y debe ser despedido en el acto (doubtfull).
2. Me falta algo claramente, debo ser excluido de Stackoverflow y nunca más volver a tocar nada que involucre la lógica.

Nota: Aquí hay un C++ implementation of the algorithm de Niek Sanders. Creo que él implementó correctamente la idea y, como tal, tiene el mismo problema (¿o no?).

Answer 1

El algoritmo solo funciona cuando el conjunto tiene una mayoría: más de la mitad de los elementos son iguales. AAACCBB en su ejemplo no tiene dicha mayoría. La carta más frecuente se produce 3 veces, la longitud de cadena es de 7.

Answer 2

Desde la primera vinculado SO pregunta:

con la propiedad de que más de la mitad de las entradas de la matriz son iguales a N

Desde la página de Boyer y Moore:

que elemento de una secuencia se encuentra en la mayoría, siempre hay un elemento tal

Ambos algoritmos suponen explícitamente que un elemento se produce al menos N/2 veces. (Nótese en particular que "mayoría" no es lo mismo que "más común".. ")

Answer 3

Pequeño pero una importante adición a las otras explicaciones algoritmo de votación de Moore tiene 2 partes -.

1. primera parte de ejecutar el algoritmo de votación de Moore sólo le da un candidato para el elemento mayoría Aviso la palabra "candidato" aquí.

2. En la segunda parte, tenemos que iterar sobre la matriz una vez más para determinar si este candidato se produce número máximo de veces (es decir, mayores que el tamaño/2 veces).

primera iteración es encontrar el candidato & segunda iteración es comprobar si este elemento se produce la mayoría de las veces en la matriz dada.

Así complejidad del tiempo es: O(n) + O(n) ≈ O(n)

Answer 4

me escribió un código C++ para este algoritmo

char find_more_than_half_shown_number(char* arr, int len){ 
int i=0; 
std::vector<int> vec; 
while(i<len){ 
    if(vec.empty()){  
     vec.push_back(arr[i]); 
     vec.push_back(1); 
    }else if(vec[0]==arr[i]){ 
     vec[1]++; 
    }else if(vec[0]!=arr[i]&&vec[1]!=0){ 
     vec[1]--; 
    }else{     
     vec[0]=arr[i]; 
    } 
    i++; 
} 
int tmp_count=0; 
for(int i=0;i<len;i++){ 
    if(arr[i]==vec[0]) 
     tmp_count++; 
} 
if(tmp_count>=(len+1)/2) 
    return vec[0]; 
else 
    return -1; 
} 

y la función principal es la siguiente:

int main(int argc, const char * argv[]) 
{ 
    char arr[]={'A','A','A','C','C','B','B','C','C','C','B','C','C'}; 
    int len=sizeof(arr)/sizeof(char); 
    char rest_num=find_more_than_half_shown_number(arr,len); 
    std::cout << "rest_num="<<rest_num<<std::endl; 
    return 0; 
} 

Answer 5

Cuando el caso de prueba es " AAACCBB ", el conjunto no tiene mayoría. Debido a que ningún elemento se produce más de 3 veces ya que la longitud de la "AAACCBB" es 7.

Aquí está el código para "Boyer y la de Moore lineal votando tiempo Algoritmo":

int Voting(vector<int> &num) { 
     int count = 0; 
     int candidate; 

     for(int i = 0; i < num.size(); ++i) { 
      if(count == 0) { 
       candidate = num[i]; 
       count = 1; 
      } 
      else 
       count = (candidate == num[i]) ? ++count : --count; 
     } 
     return candidate; 
    }