复杂性和搜索

Question

创建单词列表trie的复杂性是多少？在该单词树中搜索其他单词集的复杂程度是多少？ 我应该使用trie进行字符串搜索，当我有散列表吗？

Answer 1

的创建特里结构的复杂性是O(W*L)，其中W是单词的数目，并L是字的平均长度：你需要平均进行L查找针对每个所述组中的W字。

查找单词后也是一样：您对每个W单词执行L步骤。

散列插入和查找具有相同的复杂性：对于每个单词，您需要检查相等性，其中需要O(L)，整体复杂度为O(W*L)。

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