Какова временная сложность поиска в ориентированных ациклических графах слов?

Question

A ориентированный ациклический граф слов - отличная структура данных для определенных задач. Хотя я не могу найти никакой информации о сложности выполнения поиска.

Полагаю, это зависит линейно от средней длины слова и логарифмически от количества слов в графе.

Так ли это O(L * log W), где W - количество слов, а L - средняя длина слова?

Answer 1

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

Answer 2

Я бы сказал, что это просто O(L).Для каждого поиска слова из n символов вы всегда следуете не более n ребер, независимо от количества других ребер.

(Это предполагает стандартDAWG, в которой у каждого узла есть исходящие ребра для каждой буквы алфавита, т. Е. Для английского языка 26. Даже если у вас меньше исходящих ребер на узел и, следовательно, больше уровней, количество ребер, которым нужно следовать, по-прежнему не больше постоянного кратного n , поэтому мы все равно получаем O(L).)

Сколько слов у вас уже есть в вашей структуре, кажется, не имеет значения.

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