Berechnen den Modus (häufigster Element) ein Satz linear in der Zeit?

Question

In dem Buch "The Algorithm Design Manual" von Skiena, Berechnung der Modus (häufigster Element) eines Satzes, wobei ein O haben ( n log n ) untere Grenze (dieses Rätsels mich), aber auch (richtig glaube ich), dass kein schnelle Worst-case-Algorithmus zur Berechnung des Modus existiert. Ich bin verwirrt nur durch die untere Grenze ist, O ( n log n ).

Sehen Sie die Seite des Buches auf Google Books

Aber sicherlich könnte dies in einigen Fällen in linearer Zeit (best case) berechnet werden, z.B. von Java-Code wie unten (Funden der häufigste Zeichen in einem String), der „Trick“ zu seinem Vorkommen zählt eine Hash-Tabelle verwendet wird. Dies scheint offensichtlich.

Also, was soll ich in meinem Verständnis des Problems fehlt?

EDIT: (Rätsel gelöst) Wie StriplingWarrior weist darauf hin, die untere Grenze gilt, wenn nur Vergleiche verwendet werden, dh keine Indizierung von Speichern, siehe auch: 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

Der Autor scheint auf der Annahme, seine Logik zu stützen, dass Vergleich ist der einzige Betrieb zur Verfügung. Mit Hilfe eine Hash-basierte Datenstruktur Art wird um diesen durch die Wahrscheinlichkeit verringert benötigen, um in zu tun Vergleiche die meisten Fälle zu dem Punkt, wo man im Grunde diese in konstanter Zeit tun kann .

Wenn jedoch die Zahlen sind handverlesen, um immer Hash-Kollisionen zu erzeugen, würden Sie effektiv Ihr Hash-Set in eine Liste drehen am Ende, die Ihren Algorithmus in O (n²) machen würden. Wie der Autor weist darauf hin, das Sortieren einfach die Werte in eine Liste zuerst die besten bietet garantiert Algorithmus, obwohl in den meisten Fällen ein Hash-Set vorzuziehen wäre.

Answer 2

Also, was soll ich in meinem Verständnis des Problems fehlt?

In vielen Fällen, insbesondere, ein Array oder ein Hash-Tabelle genügt. Im „allgemeinen Fall“ tut es nicht, weil Hash-Tabelle Zugang nicht immer konstante Zeit ist.

Um zu garantieren konstanten Zeitzugriff müssen Sie in der Lage sein, zu garantieren, dass die Anzahl der Schlüssel, die möglicherweise in jedem Fach wird durch eine Konstante begrenzt am Ende kann. Für Zeichen ist dies recht einfach, aber wenn die eingestellten Elemente waren, sagt sie, Doppel- oder Strings, wäre es nicht (außer im rein akademischen Sinne, dass es beispielsweise eine endliche Anzahl von Doppelwerten).

Answer 3

Hash-Tabelle Lookups sind amortisierten konstante Zeit, das heißt in der Regel die Gesamtkosten des Nachschlagens n Zufallsschlüssel ist O (n). Im schlimmsten Fall können sie linear sein. Während also im Allgemeinen könnten sie die Reihenfolge der Modus Berechnung auf O (n) reduzieren, im schlimmsten Fall wäre es Anstieg die Reihenfolge der Modus Berechnung auf O (n ^ 2).