Какова сложность создания trie списка слов и сложность поиска другого набора слов в этом trie? Должен ли я использовать trie для поиска строк, когда у меня есть hashtable?
Trie сложность и поиск
Ответ 1
Сложность создания trie O(W*L), где W - количество слов, а L - средняя длина слова: вам нужно выполнить поиск L в среднем по каждому из слова W в наборе.
То же самое относится к поиску слов позже: вы выполняете шаги L для каждого из слов W.
Вставки и поиск хешей имеют одинаковую сложность: для каждого слова вам нужно проверить равенство, которое принимает O(L) для общей сложности O(W*L).
Если вам нужно посмотреть целые слова, хеш-таблицу проще. Однако вы не можете искать слова по их префиксу, используя хеш-таблицу; Если запросы на основе префикса вас не интересуют, используйте хеш-таблицу; в противном случае используйте trie.
Ответ 2
Три лучше для поиска префиксов и реализации автозаполнения.
Хеш-таблица рекомендуется для простого поиска.