使用 Trie 的时间复杂度为 O(m) 的单词搜索 - m 是单词的大小
Word Search with time complexity of O(m) using Trie - m is size of word
我一直在尝试一种在 O(w) 时间内 运行s 的算法，其中 w 是我试图在按字母顺序排列的单词列表中查找的单词的长度。 Space 不是问题。我找到了一些关于使用 Trie 在 O(w) 时间内查找单词的信息，但我不确定这段时间是否包括构建 Trie 本身所需的时间？假设我有一个按字母顺序排列的单词数组 S，我想找到一个单词 w，S 有 n 个单词，w 的长度为 m。这是我目前所拥有的：
1. build Trie, T, from S // O(?) time
2. search for w in T // O(m) time
我想找到一种方法使第 2 步保持恒定时间，这样我的总时间复杂度将为 O(m)。有没有办法做到这一点？如果是这样，我只需要一些关于如何设置它的指导。如果没有，我是否忘记了另一种数据结构？ Space消费不是问题。我可以根据需要使用尽可能多的 space 来使算法在 O(w) 中达到 运行，但我似乎做不到，除非我可以在恒定时间内设置 Trie。
我发现 this post 说明创建 Trie 的时间是 O(n*l)，其中 l 是 S 中单词的平均长度。这可能告诉我我需要为我的解决方案使用不同的数据结构，但我无法确定哪种其他数据结构类型适合我的问题。
通常，人们会创建一个 Trie 或其他一些数据结构，如哈希 mpap，只创建一次，然后在每次需要查找单词时重新使用它。如果您被允许这样做，那么您可以或多或少地忽略创建 Trie 的成本，并专注于在该 Trie 中查找单词的时间，正如您所注意到的那样，O(m).
请注意，如果您只是 "given" 一个按字母顺序排列的单词数组，某人在某个地方支付了 O(n * m) 的价格从磁盘、数据库中读取所有这些单词，或其他东西并将它们放入列表中。如果他们必须对数组进行排序，他们需要支付额外的费用。请注意，您可以在相同的 O(n*m) 时间内从磁盘（或从 DB，或它们来自的任何地方）读取所有单词并读入 Trie，因此，在某种意义上，构建 Trie 是 "free" 只要这个特别的挑战允许您构建树而不是被迫使用排序数组。
如果挑战是给你一个排序的单词数组和一个要查找的单词作为输入，而你每次花时间修改该数组 "counts"，那么我认为你运气不好.你可以在 O(log(n) * w) 的排序数组中找到一个词，但你不能做得比这更好。
我一直在尝试一种在 O(w) 时间内 运行s 的算法，其中 w 是我试图在按字母顺序排列的单词列表中查找的单词的长度。 Space 不是问题。我找到了一些关于使用 Trie 在 O(w) 时间内查找单词的信息，但我不确定这段时间是否包括构建 Trie 本身所需的时间？假设我有一个按字母顺序排列的单词数组 S，我想找到一个单词 w，S 有 n 个单词，w 的长度为 m。这是我目前所拥有的：
1. build Trie, T, from S // O(?) time
2. search for w in T // O(m) time
我想找到一种方法使第 2 步保持恒定时间，这样我的总时间复杂度将为 O(m)。有没有办法做到这一点？如果是这样，我只需要一些关于如何设置它的指导。如果没有，我是否忘记了另一种数据结构？ Space消费不是问题。我可以根据需要使用尽可能多的 space 来使算法在 O(w) 中达到 运行，但我似乎做不到，除非我可以在恒定时间内设置 Trie。
我发现 this post 说明创建 Trie 的时间是 O(n*l)，其中 l 是 S 中单词的平均长度。这可能告诉我我需要为我的解决方案使用不同的数据结构，但我无法确定哪种其他数据结构类型适合我的问题。
通常，人们会创建一个 Trie 或其他一些数据结构，如哈希 mpap，只创建一次，然后在每次需要查找单词时重新使用它。如果您被允许这样做，那么您可以或多或少地忽略创建 Trie 的成本，并专注于在该 Trie 中查找单词的时间，正如您所注意到的那样，O(m).
请注意，如果您只是 "given" 一个按字母顺序排列的单词数组，某人在某个地方支付了 O(n * m) 的价格从磁盘、数据库中读取所有这些单词，或其他东西并将它们放入列表中。如果他们必须对数组进行排序，他们需要支付额外的费用。请注意，您可以在相同的 O(n*m) 时间内从磁盘（或从 DB，或它们来自的任何地方）读取所有单词并读入 Trie，因此，在某种意义上，构建 Trie 是 "free" 只要这个特别的挑战允许您构建树而不是被迫使用排序数组。
如果挑战是给你一个排序的单词数组和一个要查找的单词作为输入，而你每次花时间修改该数组 "counts"，那么我认为你运气不好.你可以在 O(log(n) * w) 的排序数组中找到一个词，但你不能做得比这更好。