Сложность в использовании бинарного поиска и Trie

Question

учитывая большой список отсортированных по алфавиту слов в файле, мне нужно написать программу, которая, учитывая слово x, определяет, есть ли x в списке. Предварительная обработка в порядке, так как я буду вызывать эту функцию много раз для разных входов.
приоритеты: 1. скорость. 2. память

Я уже знаю, что могу использовать (n - количество слов, m - средняя длина слов) 1. три, время - O (log (n)), пробел (лучший случай) - O (log (n m)), пробел (худший случай) - O (n m).
2. загрузить полный список в память, затем двоичный поиск, время O (log (n)), пространство O (n * m)

Я не уверен насчет сложности на три, пожалуйста, поправьте меня, если они не правы. И есть ли другие хорошие подходы?

Answer 1

Это время O (m) для дерева и до O (m log (n)) для двоичного поиска. Пространство асимптотически равно O (n m) для любого приемлемого метода, который вы, возможно, можете уменьшить в некоторых случаях, используя сжатие. Структура дерева в теории несколько лучше в памяти, но на практике в деталях реализации скрываются черты: память, необходимая для хранения указателей и потенциально плохой доступ к кешу.

Существуют и другие варианты реализации структуры множеств - hashset и treeset - простой выбор в большинстве языков. Я бы выбрал хэш-набор, поскольку он эффективен и прост.

Answer 2

Я думаю, что HashMap отлично подходит для вашего случая, поскольку сложность времени для операций put и get равна O (1). Он отлично работает, даже если у вас нет отсортированного списка. !!!

Answer 3

Используйте фильтр Блума. Он экономит место даже для очень больших данных и представляет собой метод быстрого отклонения.

Answer 4

Я бы порекомендовал хэш-карту. Вы можете найти расширение для C ++ для этого как в VC, так и в GCC.

Answer 5

Предварительная обработка в порядке, так как я буду вызывать> эту функцию много раз входы.

В качестве пищи для размышления, вы рассматриваете создание набора из входных данных и затем поиск с использованием определенного хэша? Для создания набора потребуется больше времени, но если количество входов ограничено и вы можете вернуться к ним, тогда набор может быть хорошей идеей с O (1) для операции «содержит» для хорошей хэш-функции.