尝试复杂性和搜索 [英] Trie complexity and searching

问题描述

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

What is the complexity of creating a trie of a list of words and what is complexity of searching other set of word in that trie? Should I use trie for string searching, when i have hashtable?

推荐答案

创建一个 trie 的复杂度是 O(W*L)，其中 W 是数字L 是单词的平均长度:您需要对中的每个 W 单词的平均值执行 L 查找集合.

The complexity of creating a trie is O(W*L), where W is the number of words, and L is an average length of the word: you need to perform L lookups on the average for each of the W words in the set.

稍后查找单词也是如此:您对每个 W 单词执行 L 步骤.

Same goes for looking up words later: you perform L steps for each of the W words.

哈希插入和查找具有相同的复杂性:对于每个单词，您需要检查相等性，这需要 O(L)，对于 O(W*L)<的整体复杂性/代码>.

Hash insertions and lookups have the same complexity: for each word you need to check equality, which takes O(L), for the overall complexity of O(W*L).

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

If you need to look up entire words, hash table is easier. However, you cannot look up words by their prefix using a hash table; If prefix-based lookups are of no interest to you, use a hash table; otherwise, use a trie.

这篇关于尝试复杂性和搜索的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！