運行時間有效的算法檢查字符串與有限的內存衝突

Question

我有一個很大但有限的一組字符串，這是非常不可能的任何兩個這些字符串是相同的，但這正是我想檢查。 所有字符串大約相同長度+/- 1個字符。我們假設一個例子（但數字可能會改變），我有一套300億字符串，每個字符串大約30個字符長。在一個天真的方法中，我會把它們全部填入哈希中並檢查是否有衝突。這實際上是O（n）運行時。

由於內存是限制因素，我不能將所有字符串填充到內存中，所以我必須對數據集進行分區。假設我可以在內存中填充1億個字符串，並檢查另一個字符串對這1億個基本上是O（1）運行時。

我的高效算法（就運行時而言）會是什麼樣子？

Answer 1

如果你有N字符串，你可以在內存中保留k，那麼你有權N/k分區，每個字符串應該只有一次散列但相比N/k - 1倍。因此複雜性應該是O(N^2/k)。