Вычисление режима (самый частый элемент) набора в линейное время?

Question

В книге «Руководство по проектированию алгоритма» Skiena вычисляет Режим (Наиболее частый элемент) набора, называется Ω (N. журнал N.) Нижняя оценка (это озадачивает меня), но и (правильно я думаю), что не существует быстрее алгоритма худшего случая для вычисления режима. Я только озадачен более низким обязанным существом Ω (N. журнал N.).

Смотрите страницу книги на Google Книги

Но, безусловно, в некоторых случаях это может быть вычислено в линейном времени (лучший случай), например, с помощью кода Java, как ниже (находит наиболее частый символ в строке), «трюк», чтобы подсчитать происшествия, используя Hashtable. Это кажется очевидным.

Итак, что я скучаю по моим пониманию проблемы?

Редактировать: (Тайна решена) Как отмечает striplingwarrior, нижняя граница держит, если используются только сравнения, то есть отсутствие индексации памяти, см. Также: http://en.wikipedia.org/wiki/element_distictness_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

Автор, кажется, основывает свою логику на предположении, что сравнение Это единственная операция доступна для вас. Использование структуры данных на основе хэшей вроде обойти это, уменьшая вероятность того, что нужно сделать сравнения в большинство случаев до такой степени, что вы можете в основном сделать это в постоянное время.

Тем не менее, если числа были выбраны вручную, чтобы всегда производить колесные столкновения, вы будете в конечном итоге эффективно превращать вашу HASH, установленные в список, что сделало бы ваш алгоритм в O (n²). Как указывает автор, просто сортировка значений в список сначала обеспечивает лучшее гарантировано Алгоритм, хотя в большинстве случаев набор хеш будет предпочтительным.

Answer 2

Итак, что я скучаю по моим пониманию проблемы?

Во многих конкретных случаях хватает массив или хэш таблицы. В «общем случае» это не так, потому что доступ к хэш-таблицу не всегда постоянна.

Чтобы гарантировать постоянный доступ в течение времени, вы должны быть в состоянии гарантировать, что количество ключей, которые могут быть в конечном итоге в каждом корзине, ограничены некоторой постоянной. Для персонажей это довольно легко, но если установленные элементы были, скажем, удваиваются или строки, это не было бы (за исключением чисто академического смысла, например, конечное количество двойных значений).

Answer 3

Hash Thap Lookups - это амортизация постоянного времени, т. Е. В общем, общая стоимость взгляда на случайных клавишных клавиш - это O (n). В худшем случае они могут быть линейными. Следовательно, в то время как в целом они могут уменьшить порядок расчета режима к O (n), в худшем случае это увеличивать Порядок расчета режима к O (N ^ 2).