有向非循环词图中查找的时间复杂度是多少？
有向无环词图对于某些任务来说是一种很好的数据结构。不过，我找不到有关执行查找的时间复杂度的任何信息。
我猜想它与平均字长呈线性关系，与图中的字数呈对数关系。
那么是O(L * log W)吗，其中W是单词数，L是平均单词长度？
A directed acyclic word graph is a great data structure for certain tasks. I can't find any information on the time complexity of performing a lookup though.
I would guess it depends linearly on the average word length, and logarithmically on the number of words in the graph.
So is it O(L * log W), where W is the number of words and L is the average word length?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
我认为复杂度只是 O(L)。操作的数量与单词的长度成正比，并且结构有多少个条目并不重要。 （根据节点搜索的实现可能存在差异，但在最坏的情况下，最坏的实现只是恒定的上限等于字母表的大小）
I think that complexity is just O(L). Number of operations is proportional to length of word and it does not matter how many entries structure have. (there might be differences based on implementation of node searching but that is in worst case and worst implementation just constant whit upper limit equal to size of alphabet)
我想说这只是
O(L)。对于每次查找包含 n 个字符的单词，您始终最多遵循 n 个边，而不管还有多少个其他边。（假设有一个标准 DAWG，其中每个节点对于字母表中的每个字母都有传出边，即英语有 26 个传出边。即使每个节点的传出边较少，因此层数较多，要遵循的边数最多仍然是n 的常量倍数，因此我们仍然得到
O(L)。）结构中已有多少个单词似乎无关紧要。
即使在每一步中，您都对从当前节点开始的正确边执行线性搜索，这仍然是常数时间，因为字母表是有界的，因此每个节点的传出边的数量也是有界的。
I’d say it’s just
O(L). For each lookup of a word of n characters, you always follow at most n edges, irrespective of how many other edges there are.(That’s assuming a standard DAWG in which each node has outgoing edges for every letter of the alphabet, i.e. 26 for English. Even if you have fewer outgoing edges per node and therefore more levels, the number of edges to follow is still at most a constant multiple of n, so we still get
O(L).)How many words you already have in your structure seems to be irrelevant.
Even if, at each step, you perform a linear search for the correct edge to follow from the current node, this is still constant-time because the alphabet is bounded, and therefore so is the number of outgoing edges from each node.