映射函数以减少时间复杂度？博士学位项目

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的变体，这是表示一个集合的概率方式。使用布隆过滤器 - 你可能会有误报（假设某些东西在集合中，但不是），但从来不会出现假阴性（假设它不是整数集合中的某个）。