Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

5.2.2 Trie的时间复杂度 #526

Open
mooxiu opened this issue Dec 7, 2020 · 3 comments
Open

5.2.2 Trie的时间复杂度 #526

mooxiu opened this issue Dec 7, 2020 · 3 comments
Assignees
@cch123

Comments

@mooxiu
Copy link

mooxiu commented Dec 7, 2020

字典树常用来进行字符串检索，例如用给定的字符串序列建立字典树。对于目标字符串，只要从根节点开始深度优先搜索，即可判断出该字符串是否曾经出现过，时间复杂度为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
Copy link
Collaborator

cch123 commented Dec 17, 2020 •
edited

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

@cch123 cch123 self-assigned this Dec 17, 2020
@mooxiu
Copy link
Author

mooxiu commented Dec 17, 2020

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

@cch123
Copy link
Collaborator

cch123 commented Dec 17, 2020

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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees

@cch123 cch123

Labels
None yet
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
2 participants
@cch123 @mooxiu