¿Computando el modo (elemento más frecuente) de un conjunto en tiempo lineal?

Question

En el libro "El Algoritmo Manual de diseño" por Skiena, el cálculo de la modo (elemento más frecuente) de un conjunto, se dice que tiene una Ω (n registro n) cota inferior (esto me intriga) , pero también (correctamente supongo) que no existe un algoritmo de peor caso más rápido para calcular el modo. Solo me deja perplejo que el límite inferior sea Ω (n log n).

Véase la página del libro en Google Books

Pero sin duda esto podría en algunos casos ser calculado en tiempo lineal (mejor de los casos), por ejemplo, por código Java como a continuación (encuentra el carácter más frecuente en una cadena), el "truco" es contar las ocurrencias usando una tabla hash. Esto parece obvio.

Entonces, ¿qué es lo que me falta en mi comprensión del problema?

EDIT: (Misterio resuelto) Como StriplingWarrior señala, el límite inferior se mantiene si sólo se utilizan comparaciones, es decir, sin la indexación de la memoria, ver también: http://en.wikipedia.org/wiki/Element_distinctness_problem

// Linear time 
char computeMode(String input) { 
    // initialize currentMode to first char 
    char[] chars = input.toCharArray(); 
    char currentMode = chars[0]; 
    int currentModeCount = 0; 
    HashMap<Character, Integer> counts = new HashMap<Character, Integer>(); 
    for(char character : chars) { 
    int count = putget(counts, character); // occurences so far 
    // test whether character should be the new currentMode 
    if(count > currentModeCount) { 
     currentMode = character; 
     currentModeCount = count; // also save the count 
    } 
    } 
    return currentMode; 
} 

// Constant time 
int putget(HashMap<Character, Integer> map, char character) { 
    if(!map.containsKey(character)) { 
    // if character not seen before, initialize to zero 
    map.put(character, 0); 
    } 
// increment 
    int newValue = map.get(character) + 1; 
    map.put(character, newValue); 
    return newValue; 
} 

Answer 1

El autor parece estar basando su lógica en el supuesto de que comparación es la única operación disponible para usted. El uso de una estructura de datos basada en hash tipo de soluciona esto al reducir la probabilidad de tener que hacer comparaciones en la mayoría de los casos hasta el punto donde básicamente puede hacer esto en tiempo constante.

Sin embargo, si los números fueron seleccionados a mano para producir siempre colisiones hash, terminaría efectivamente convirtiendo su hash en una lista, lo que haría que su algoritmo sea O (n²). Como señala el autor, simplemente ordenar los valores en una lista primero proporciona el mejor algoritmo garantizado, aunque en la mayoría de los casos sería preferible un conjunto de hash.

Answer 2

Entonces, ¿qué me falta en mi comprensión del problema?

En muchos casos particulares, una matriz o tabla hash es suficiente. En "el caso general" no es así, porque el acceso a la tabla hash no siempre es un tiempo constante.

Para garantizar el acceso constante en el tiempo, debe ser capaz de garantizar que el número de claves que posiblemente puede terminar en cada contenedor está limitado por una constante. Para los personajes esto es bastante fácil, pero si los elementos establecidos fueran, por ejemplo, dobles o cadenas, no lo serían (excepto en el sentido puramente académico de que hay, por ejemplo, un número finito de valores dobles).

Answer 3

Las búsquedas de tablas hash se amortizan a tiempo constante, es decir, en general, el costo total de buscar n claves aleatorias es O (n). En el peor de los casos, pueden ser lineales. Por lo tanto, aunque en general podrían reducir el orden del cálculo del modo a O (n), en el peor de los casos aumentaría el orden del cálculo del modo a O (n^2).