Computar el modo (elemento más frecuente) de un conjunto en el 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 O ( n registro n ) límite inferior (este juego de puzzles Me), sino también (correctamente supongo) que no existe más rápido peor de los casos algoritmo para calcular el modo. Sólo estoy sorprendido por el límite inferior es O ( n Registro n ).

Ver la página del libro en Google Books

Pero seguramente 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 (no encuentra el carácter más frecuente en una cadena), el "truco" ser para contar las ocurrencias utilizando una tabla hash. Esto parece obvio.

Por lo tanto, lo que me falta en mi comprensión del problema?

EDIT: (Mystery resuelto) Como StriplingWarrior señala, sostiene el límite inferior si sólo se utilizan comparaciones, es decir, sin la indexación de la memoria, véase 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 a su disposición. El uso de una estructura de datos basada en Hash tipo de evita esto mediante la reducción de la probabilidad de necesitar hacer comparaciones en la mayoría de los casos a tal punto que básicamente se puede hacer esto en un tiempo constante .

Sin embargo, si los números eran siempre para producir colisiones hash a dedo, que llevaría a considerar que efectivamente el conjunto de hash en una lista, lo que haría que su algoritmo en O (N ²). Como señala el autor, sólo tiene que ordenar los valores en una lista primero ofrece la mejor garantizada algoritmo, a pesar de que en la mayoría de los casos un conjunto de hash sería preferible.

Answer 2

Por lo tanto, lo que me falta en mi comprensión del problema?

En muchos casos particulares, una matriz o de hash basta mesa. En "el caso general" no es así, porque el acceso tabla hash no es siempre constante de tiempo.

Con el fin de garantizar el acceso constante de tiempo, usted debe ser capaz de garantizar que el número de teclas que, posiblemente, puede terminar en cada bandeja está limitado por alguna constante. Para los caracteres esto es bastante fácil, pero si los elementos de ajuste eran, por ejemplo, dobles o cadenas, no sería (excepto en el sentido puramente académico que hay, por ejemplo, un número finito de valores dobles).

Answer 3

búsquedas de tabla Hash son el tiempo constante amortizado, es decir, en general, el coste global de mirando hacia arriba teclas n aleatorios es O (n). En el peor de los casos, pueden ser lineales. Por lo tanto, mientras que, en general, que podría reducir el orden de cálculo de modo en O (n), en el peor de los casos que lo haría aumento el orden de cálculo de modo en O (n ^ 2).