搜索方法数据结构

Question

我对分发给我的论文中的一个问题有一个问题，我希望有人能给我一些帮助。问题是：

a)以计算机可搜索的形式存储具有100个标题的鸟类的小书和具有1000个标题的鸟类的大书。搜索大型鸟类书籍所需的时间大约是小型鸟类书籍的50%。使用哪种搜索方法？

b)现在交换存储和搜索方法。现在，搜索这两本书所需的时间相同。哪种是新的搜索方法？

所以第一个问题的复杂度是O(log(n))，而我不知道任何搜索方法的时间复杂度。第二个应该是O(1)阶的，因为它们需要相同的时间？？

Answer 1

Binary search具有渐近复杂性O(log n)。如果假设标题的长度是恒定的，则hash-based算法可以在恒定的时间内检索元素，参见例如hash tables。