假设我有一个数据库:
k篇文章- 每篇文章都有一个包含
l个单词的标题 - 我的搜索查询有
m个标记
在所有文章的标题中搜索我的每个标记是m * k * l
我认为这是 O(n) 是否正确？
最佳答案
接下来，我将假设每个单词的长度不超过 w。
除非在某处定义了 n，否则谈论 O(n) 时间在数学上是无效的。如果您将 n 解释为给定输入的总长度(写出所有文章和搜索查询所需的位数)，那么您将得到 n = (kl + m)w。
请注意，您的算法不会在时间 O(mlk) 内运行，除非 w 是常数。更准确地说，是O(mlkw)。由于 n = lkw + mw，根据对 n 的这种解释，您的运行时间不会是 O(n)。
也就是说 - 您可以通过使用更好的数据结构显着提高算法的运行时间。如果你构建一个 trie包含你所有的单词(这需要时间 mw)，然后你可以在时间 O(w) 中查找每个单词。这意味着由于总共有 kl 个单词需要考虑，您的搜索时间将为 O(mw + lkw)， 是线性的。
希望这对您有所帮助!
关于algorithm - 搜索本文数据库的复杂性，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/19452957/