Сложность trie

Question

Как полезно использовать trie, если нужно хотя бы прочитать все символы из входного массива строк, чтобы вставлять строки один за другим в trie? Таким образом, сложность O (size_of_array). Предположим, что входной массив строк равен {"hello",world","stack","overflow"}, и мы хотим найти «стек», тогда нам нужно было бы хотя бы пройти весь массив для вставки ключей в trie. Таким образом, сложность - O (size_of_array). Мы могли бы сделать это без трюка.

Answer 1

Пункт три для многих запросов.

• Трое предлагает относительно дешевую вставку каждой строки.
• Трое предлагает относительно дешевый поиск строки.

Это означает, что если у вас есть массив, и вам нужно запросить существование строки в нем только один раз - это, вероятно, не очень полезно, так как создание trie для одного запроса является расточительным.

Однако, если у вас есть словарь, и вы будете запрашивать его в следующие миллионы раз - это значительно эффективнее для поиска в trie, чем для повторного поиска массива - и именно там вы его извлекаете.

Answer 2

Испытания действительно полезны в менее распространенных случаях. Но они используют их.

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

2. Предположим, у вас есть словарь действительно длинных строк, и вы хотите проверить, нет ли в нем новой очень длинной строки. Затем, используя хеширование, вам нужно будет перебрать каждую букву новой строки. Используя trie, вы, возможно, сможете это исключить очень быстро.