Le mode de calcul (plus d'élément fréquent) d'un ensemble dans le temps linéaire?

Question

Dans le livre "L'algorithme de conception manuelle" par Skiena, le calcul du mode (élément le plus fréquent) d'un ensemble, est dit d'avoir un O ( n log n ) bas lié (ce casse-tête me), mais aussi (à juste titre je suppose) qu'aucun algorithme plus rapide pire cas existe pour calculer le mode. Je ne laisse perplexe la borne inférieure étant O ( n log n ).

  

Voir la page du livre sur Google Livres

Mais sûrement cela pourrait dans certains cas, être calculé en temps linéaire (meilleur cas), par exemple par le code Java comme ci-dessous (trouve le plus de caractères fréquents dans une chaîne), le « truc » étant de compter occurences en utilisant une table de hachage. Cela semble évident.

Alors, qu'est-ce que je manque dans ma compréhension du problème?

EDIT: (Mystère résolu) Comme StriplingWarrior souligne, la limite inférieure tient si seules les comparaisons sont utilisées, à savoir pas d'indexation de la mémoire, voir aussi: 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

L'auteur semble baser sa logique sur l'hypothèse que comparaison est la seule opération à votre disposition. En utilisant une structure de données à base de hachage sorte de contourne cela en réduisant la probabilité d'avoir besoin de faire des comparaisons dans la plupart des cas au point où vous pouvez essentiellement faire en temps constant .

Cependant, si les chiffres ont été cueillies à la main pour produire toujours des collisions de hachage, vous finiriez transformant votre jeu de hachage dans une liste, ce qui rendrait votre algorithme en O (n²). Comme le souligne l'auteur, tout simplement trier les valeurs dans une première liste fournit les meilleurs garantie algorithme, même si dans la plupart des cas, un ensemble de hachage serait préférable.

Answer 2

  

Alors, qu'est-ce que je manque dans ma compréhension du problème?

Dans de nombreux cas particuliers, une table suffit tableau ou de hachage. Dans « le cas général », il n'a pas, parce que l'accès de la table de hachage est pas toujours constante de temps.

Afin de garantir un accès à temps constant, vous devez être en mesure de garantir que le nombre de clés qui peuvent éventuellement se retrouver dans chaque cellule est limitée par une constante. Pour les caractères cela est assez facile, mais si les éléments de l'ensemble étaient, disons, doubles ou des chaînes, il ne serait pas (sauf dans le sens purement académique qu'il ya, par exemple, un nombre fini de valeurs doubles).

Answer 3

tables de référence de Hash sont à temps constant amorti, à savoir, en général, le coût global de la recherche des clés aléatoires n est O (n). Dans le pire des cas, ils peuvent être linéaires. Par conséquent, alors qu'en général ils pourraient réduire l'ordre de calcul du mode O (n), dans le pire des cas, il serait augmentation l'ordre de calcul du mode O (n ^ 2).