В литературе много информации, в которой говорится, что время поиска trie - это O (N), где N - длина шаблона.Сколько времени занимает создание trie
Однако, построение дерева также займет некоторое время. Для меня, скажем, есть X слов с общим количеством символов Y.
Итак, тогда O (Y) - это время (потому что мы должны вставлять каждый символ). Является ли эта оценка правильной (обычно я ошибаюсь)
Неверно. Создание trie и поиск trie - это два разных алгоритма. Нельзя строить три, искать его, а затем выбрасывать всю структуру данных.
Вы правы в том, что trie следует использовать много раз. Однако ваш ответ неверен, поскольку вы утверждаете, что OP ошибочен. – maaartinus
Итак O (Y) является время (потому что мы должны вставить каждый символ)
Конечно, вы должны обрабатывать каждый входной символ, и либо следовать существующей ветви или вставить новый голец.
Это не может быть быстрее, чем O (Y), так как вы должны смотреть на каждый входной символ. Нет ни сортировки, ни какой-либо другой операции, которая могла бы сделать ее медленнее.
Время вставки х элементов для вставки. С головы до головы O (nlogn). – leppie