Var*_*run 21 algorithm hashtable trie time-complexity data-structures
什么是创建一个复杂线索单词列表的,什么是该线索寻找另一组字的复杂性？当我有哈希表时,我应该使用trie进行字符串搜索吗？
das*_*ght 29
创建trie的复杂性是O(W*L),W单词的数量,以及单词L的平均长度:您需要对集合中的L每个W单词执行平均查找.
稍后查找单词也是如此:您L为每个W单词执行步骤.
散列插入和查找具有相同的复杂性:对于每个单词,您需要检查相等性,这需要O(L)总体复杂度O(W*L).
如果您需要查找整个单词,哈希表更容易.但是,您无法使用哈希表通过其前缀查找单词; 如果您不感兴趣基于前缀的查找,请使用哈希表; 否则,请使用特里.