Word Поиск с временной сложностью O (m) с использованием Trie-m - это размер слова

Question

Я пытаюсь использовать алгоритм, который работает в O (w) time, где w - длина слова, которое я пытаюсь найти в список алфавитно упорядоченных слов. Пространство не вызывает беспокойства. Я нашел некоторую информацию об использовании Trie, чтобы найти слово в времени O (w), но я не уверен, включает ли это время время, необходимое для создания самой Trie? Скажем, у меня есть массив отсортированных по алфавиту слов, S, и я хочу найти слово w, S имеет n слов, w имеет длину m. Вот то, что я до сих пор:

1. build Trie, T, from S // O(?) time 
2. search for w in T // O(m) time 

Я хотел бы найти способ, чтобы держать шаг 2 в постоянная время, поэтому моя общая временная сложность будет O (м). Есть ли способ сделать это? Если это так, мне нужно только некоторое руководство по настройке. Если нет, есть ли другая структура данных, о которой я прокладываю? Потребление пространства не является проблемой. Я могу использовать столько места, сколько необходимо для того, чтобы алгоритм работал в O (w), чего я не могу сделать, если только я не смогу настроить Trie в постоянное время.

Я нашел this сообщение, в котором указано время создания Trie is O (n * l), где l - длина слов в строке S. Это может мне сказать, мне нужно использовать другую структуру данных для моего решения, но я не могу определить, какой другой тип структуры данных будет соответствовать моей проблеме.

Answer 1

Как правило, можно создать Trie или какую-либо другую структуру данных, такую ​​как хэш-mpap, только один раз, а затем повторно использовать ее каждый раз, когда вам нужно найти слово. Если вам разрешено это сделать, вы можете более или менее игнорировать затраты на создание Trie и сосредоточиться на времени, чтобы найти слово в этом Trie, которое, как вы заметили, O (m).

Обратите внимание, что если вы просто «задали» массив алфавитно упорядоченных слов, то где-то заплатили цену O (n * m), чтобы прочитать все эти слова с диска, из базы данных или что-то еще включите их в список. Если им пришлось сортировать массив, они заплатили дополнительную плату. Обратите внимание, что вы можете читать все слова с диска (или из БД или откуда бы они ни были) и в Trie в том же O (n * m) времени, так что в некотором смысле создание Trie «бесплатно» «пока эта особая задача позволяет вам построить дерево вместо того, чтобы работать с отсортированным массивом.

Если проблема заключается в том, что вам задан отсортированный массив слов и слово для поиска в качестве входных данных, и в любое время, когда вы проводите изменение этого массива, «считается», я думаю, вам не повезло. Вы можете найти слово в отсортированном массиве в O (log (n) * w), но вы не можете сделать лучше этого.