5.2.2 Trie的时间复杂度

[mooxiu]

字典树常用来进行字符串检索，例如用给定的字符串序列建立字典树。对于目标字符串，只要从根节点开始深度优先搜索，即可判断出该字符串是否曾经出现过，时间复杂度为O(n)，n可以认为是目标字符串的长度。

如果Trie是二叉树那么O(n)没有问题，但多叉树的情况或许这么说不太准确？ 搜索了一些英文资料，普遍写成时间复杂度是O(W*L), W: Number of Words, L: Length.

Ref: Trie complexity and searching Trying to Understand Tries

[cch123]

@MuyaoXiao ，感谢 issue，我看了一下原文，O(W*L) 是说创建 trie 的时间复杂度，我在里面写的是搜索的

[mooxiu]

喔！每次找一层是hash的 sorry for my stupid issue

[cch123]

@MuyaoXiao ，没事，阅读过程有问题欢迎随时反馈~