假设我有一个数据库：
k文章- 每篇文章都有一个标题，里面有
l单词 - 我的搜索查询有
m标记
在所有文章的标题中搜索我的每个标记是m * k * l
我认为这是对的O(n)吗？
问问题
54 次
1 回答
1
在下文中，我将假设每个单词的长度为 w 或更短。
除非在某处定义了 n，否则谈论 O(n) 时间在数学上是无效的。如果您将 n 解释为提供给您的输入的总长度（写出所有文章和搜索查询所需的位数），那么您将得到 n = (kl + m)w。
请注意，除非 w 是常数，否则您的算法不会及时运行 O(mlk)。更准确地说，它是 O(mlkw)。由于 n = lkw + mw，根据对 n 的这种解释，您的运行时间不会是 O(n)。
也就是说 - 您可以通过使用更好的数据结构来显着提高算法的运行时间。如果您构建一个包含所有单词的trie（这需要时间 mw），那么您可以在 O(w) 时间内查找每个单词。这意味着由于要考虑的总词数为 kl，因此您的搜索时间将为 O(mw + lkw)，这是线性的。
希望这可以帮助！
于 2013-10-18T20:33:14.597 回答