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

Question

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

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

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

Итак, что мне не хватает в моем понимании проблемы?

EDIT: (Тайна решена) Как StriplingWarrior указывает, нижняя граница не имеет место, если используются только сравнения, т.е. без индексации памяти, смотрите также: 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

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

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

Answer 2

Итак, что мне не хватает в моем понимании проблемы?

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

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

Answer 3

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