映射函數以減少時間複雜度？博士學位項目

Question

這是我最後一個成績單。我給出了一個我認爲很好的答案。我們只是在考試中獲得分數，而不是我們是否有正確的問題。希望社區能夠爲此提供指導，我對於答案的興趣並不在於什麼被測試，而是在哪裏我可以更多地瞭解它，並在下次考試前進行一些練習。乍一看，它看起來像一個時間複雜性問題，但是當它開始討論映射函數和預先排序數據時，我不知道如何處理。 那麼你會如何回答？

這就是：

給定一組物品的X = {X1，X2，...，XN}從一些領域ž畫，你的任務是找到如果查詢項目●在ž發生在集合中。爲簡單起見，您可以假設每個項目在X中只出現一次，並且需要花費O（l）的時間量來比較Z中的任意兩個項目。

（a）編寫一個算法的僞代碼，十，算法的最壞情況時間複雜度是多少？ （b）如果l非常大（例如，如果X的每個元素都是一個長視頻），那麼就需要有效的算法來檢查X中是否有q \。假設你有權訪問k個函數h_i：Z-> {1,2，...，m}，它們將Z的一個元素均勻地映射到1和m之間的一個數字，並且讓l和m> n。 爲使用函數h_1 ... h_k檢查X中是否存在q \的算法編寫僞代碼。請注意，您可以預處理數據。算法的最壞情況時間複雜度是多少？

請在您的僞代碼中明確輸入，輸出和假設。

Answer 1

首先好像是一個簡單的線性掃描。時間複雜度爲O(n * l)，最糟糕的情況是比較所有元素。注意 - 因爲如果數據排序，沒有信息，所以它不能與n呈線性關係。

第二個（b）實際上是bloom-filter的變體，這是表示一個集合的概率方式。使用布隆過濾器 - 你可能會有誤報（假設某些東西在集合中，但不是），但從來不會出現假陰性（假設它不是整數集合中的某個）。