Trie复杂度和搜索

Question

创建一个单词列表的trie的复杂度是什么？在该trie中搜索其他单词集合的复杂度是什么？ 当我拥有哈希表时，我是否应该使用trie进行字符串搜索？

- Varun

Answer 1

创建一个trie的复杂度为 O(W*L)，其中W是单词数量，L是单词的平均长度：每个单词需要进行L次查找，对于集合中的W个单词都是如此。

在之后查找单词时，情况也是如此：每个单词都需要进行L次查找。

哈希表的插入和查找具有相同的复杂度：对于每个单词，您需要检查相等性，这需要O(L)的时间，因此总体复杂度为O(W*L)。

如果您需要查找整个单词，哈希表更容易。然而，使用哈希表无法通过前缀查找单词；如果基于前缀的查找对您没有兴趣，请使用哈希表；否则，请使用Trie。

- Sergey Kalinichenko

---

如果我在哈希表中查找整个单词，我需要一些好的哈希函数，而且在定义哈希函数时应该小心谨慎。如果我有任何错误，请纠正我。 - Varun

由于字符串被广泛用作哈希表的键，因此已经发明了非常好的字符串哈希函数。在互联网上快速搜索会给出半打优秀的建议。我会选择微软使用的或内置于Java字符串中的哈希函数，因为它们已经进行了很多优化。 - Sergey Kalinichenko

哈希表查找的时间复杂度不应该是 O(1) 吗？ - lordvcs

@lordvcs 只有在您认为字符串的长度是固定的或具有固定的上限时，这才是正确的，即当您将 L 视为常量而不是变量时。由于 trie 对字符串的长度敏感（它影响 trie 的高度），所以此问题的上下文不允许您这样做。 - Sergey Kalinichenko