複雜搜索這篇文章的數據庫

Question

比方說，我有一個數據庫：

• k文章
• 每篇文章有l字的標題是
• 我的搜索查詢具有m令牌

要在所有文章的標題中搜索我的每個標記是m * k * l

我是否認爲這是O(n)？

Answer 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），其中是的線性。

希望這會有所幫助！