複雜性和搜索

Question

創建單詞列表trie的複雜性是多少？在該單詞樹中搜索其他單詞集的複雜程度是多少？ 我應該使用trie進行字符串搜索，當我有散列表嗎？

Answer 1

的創建特里結構的複雜性是O(W*L)，其中W是單詞的數目，並L是字的平均長度：你需要平均進行L查找針對每個所述組中的W字。

查找單詞後也是一樣：您對每個W單詞執行L步驟。

散列插入和查找具有相同的複雜性：對於每個單詞，您需要檢查相等性，其中需要O(L)，整體複雜度爲O(W*L)。

如果您需要查找整個單詞，散列表更容易。但是，你不能用哈希表的前綴來查找單詞;如果基於前綴的查找對您不感興趣，請使用哈希表;否則，使用一個trie。