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

Question

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

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

Answer 1

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

同样，对于具有有限大小的集合（http://en.wikipedia.org/wiki/Perfect_hash_function）存在多种技术，尽管如果这些集合大小非常大，在实践中会出现问题

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

Answer 2

是的，创建一个巨大的数组，这样每个可能的值都有一个槽。存储值和查找值的时间复杂度为 O(1)。

编辑：

如果还计算初始化时间，那么绝对不可能做出 O(1) 搜索算法。在没有预处理的情况下搜索数组永远不会比 O(n) 更好，并且没有办法在 O(1) 中预处理 n 项。