language-agnostic - 建造树需要多少时间

Question

文献中有很多信息说搜索 trie 的时间是 O(N)，其中 N 是模式的长度。

但是，构建树也需要一些时间。对我来说，假设有 X 个单词，总共有 Y 个字符。

那么 O(Y) 就是时间（因为我们必须插入每个字符）。这个评估是否正确（我通常不正确）

Answer 1

那么 O(Y) 就是时间（因为我们必须插入每个字符）

当然，您必须处理每个输入字符，并遵循现有分支或插入新字符。

它不能比 O(Y) 更快，因为您必须查看每个输入字符。既没有排序也没有任何其他操作可以使它变慢。

Answer 2

错误的。创建 trie 和搜索 trie 是两种不同的算法。一个人不会建立一个 trie，搜索它，然后丢弃整个数据结构。