Calcolo del modo (più elemento frequente) di un insieme in un tempo lineare?

Question

Nel libro "L'algoritmo design manuale" di Skiena, calcolando il modalità (elemento più frequente) di un insieme, si dice che abbia un O ( n di registro n ) limite inferiore (questo mi puzzle), ma anche (giustamente credo) che non esiste alcun algoritmo più veloce nel caso peggiore per il calcolo della modalità. Sono perplesso solo dal limite inferiore essendo O ( n Registro n ).

  

Si veda la pagina del libro su Google libri

Ma sicuramente questo potrebbe in alcuni casi essere calcolata in tempo lineare (migliore dei casi), ad esempio dal codice Java come qui di seguito (viene individuato il carattere più frequente in una stringa), il "trucco" è quello di contare le occorrenze utilizzando una tabella hash. Questo sembra ovvio.

Quindi, ciò che mi manca nella mia comprensione del problema?

EDIT: (mistero risolto) Come StriplingWarrior sottolinea, il limite inferiore vale solo se si utilizzano i confronti, cioè non indicizzazione di memoria, vedere anche: 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'autore sembra essere basando la sua logica sull'assunto che confronto è l'unica operazione a vostra disposizione. Utilizzando una struttura dati hash basato su sorta di aggira questo, riducendo la probabilità di aver bisogno di fare confronti in maggior parte dei casi al punto in cui si può sostanzialmente fare questo in tempo costante .

Tuttavia, se i numeri erano raccolte a mano per la produzione di sempre collisioni hash, si finirebbe per trasformare in modo efficace il set hash in un elenco, il che renderebbe il vostro algoritmo in O (n²). Come l'autore fa notare, semplicemente l'ordinamento dei valori in un elenco prima offre la migliore garantito algoritmo, anche se nella maggior parte dei casi un set hash sarebbe preferibile.

Answer 2

  

Quindi, ciò che mi manca nella mia comprensione del problema?

In molti casi particolari, un array o hash sufficiente un tavolo. Nel "caso generale" non è così, perché l'accesso tabella di hash non è sempre costante di tempo.

Al fine di accedere in tempo garanzia di costante, è necessario essere in grado di garantire che il numero di chiavi che può eventualmente finire in ogni bin è delimitata da una costante. Per i caratteri questo è abbastanza facile, ma se gli elementi fissati erano, diciamo, doppie o stringhe, non sarebbe (se non nel senso puramente accademica che ci sono, per esempio, un numero finito di valori doppi).

Answer 3

ricerche tabella hash sono tempo costante ammortizzato, cioè, in generale, il costo complessivo di guardare chiavi n casuali è O (n). Nel peggiore dei casi, possono essere lineari. Pertanto, mentre in generale potrebbero ridurre l'ordine di calcolo modalità O (n), nel caso peggiore sarebbe incremento l'ordine di calcolo modalità O (n ^ 2).