algorithm - 尝试复杂性和搜索

Question

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

Answer 1

创建 trie 的复杂性是O(W*L)，其中W是单词的数量，并且L是单词的平均长度：您需要对集合中的L每个单词进行平均查找。W

稍后查找单词也是如此：您L为每个W单词执行步骤。

哈希插入和查找具有相同的复杂性：对于每个单词，您需要检查相等性，这需要O(L)，对于O(W*L).

如果您需要查找整个单词，哈希表更容易。但是，您不能使用哈希表通过前缀查找单词；如果您对基于前缀的查找不感兴趣，请使用哈希表；否则，使用 trie。