algorithm - 时间复杂度最小的搜索算法

Question

有没有时间复杂度O(1)的搜索算法？

搜索算法 = 从 n 个元素中查找元素 x。

Answer 1

尽管如果确定性 O(1) 的搜索算法存在我会感到惊讶，但好消息是您可以通过 O(1) 添加和使用 bloom 的查找操作获得任意接近 100% 准确度的查找筛选。 (http://en.wikipedia.org/wiki/Bloom_filter)

类似地，对于那些具有有限大小的集合 (http://en.wikipedia.org/wiki/Perfect_hash_function) 存在各种技术，尽管如果这些集合大小非常大，在实践中会出现问题

但是，就一般情况而言，据我所知，答案是否定的。当然在任何实际应用中都不会。