algorithm - 使用 Trie 的时间复杂度为 O(m) 的单词搜索 - m 是单词的大小

Question

我一直在尝试一种在 O(w) 时间内运行的算法，其中 w 是我试图在按字母顺序排列的单词列表中查找的单词的长度。空间不是问题。我找到了一些关于使用 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)。有没有办法做到这一点？如果是这样，我只需要一些关于如何设置它的指导。如果没有，我是否忘记了另一种数据结构？空间消耗不是问题。我可以根据需要使用尽可能多的空间来让算法在 O(w) 中运行，但我似乎做不到，除非我可以在恒定时间内设置 Trie。

我找到了 this帖子说明创建 Trie 的时间是 O(n*l)，其中 l 是 S 中单词的平均长度。这可能告诉我我需要为我的解决方案使用不同的数据结构，但我无法确定其他哪个数据结构类型适合我的问题。

Answer 1

通常，人们会创建一个 Trie 或其他一些数据结构，如哈希 mpap，只创建一次，然后在每次需要查找单词时重新使用它。如果您被允许这样做，那么您可以或多或少地忽略创建 Trie 的成本，并专注于在该 Trie 中查找单词的时间，正如您所注意到的，O(m)。

请注意，如果您只是“给定”了一个按字母顺序排列的单词数组，某人在某个地方支付了 O(n * m) 的代价来从磁盘、数据库或其他东西中读取所有这些单词，然后将其放入他们进入一个列表。如果他们必须对数组进行排序，他们需要支付额外的费用。请注意，您可以在相同的 O(n*m) 时间内从磁盘(或从 DB，或它们来自的任何地方)读取所有单词并读入 Trie，因此，在某种意义上，构建 Trie 是“免费的” "只要这个特别的挑战允许您构建树而不是被迫使用排序数组。

如果挑战是给定一个排序的单词数组和一个要查找的单词作为输入，并且任何时候您花在修改该数组上的时间都“很重要”，那么我认为您运气不好。您可以在 O(log(n) * w) 的排序数组中找到一个单词，但您不能做得比这更好。