为什么在排序数组中查找指定值的速度不可能快于O（log n）？

Question

对cs来说很新鲜...在一次演讲的结尾，我的AP计算机科学老师提到在排序数组中找到指定值的比较模型是“大欧米茄（log n）”，我的理解是，这意味着完成这个任务的速度不可能比O（log n）快？你能帮我弄明白为什么吗？谢谢你！

Answer 1

让我们假设您有一个由n个项组成的数组。如果在这个数组中执行查找，那么该查找可以返回n+1个值中的一个：对于n个索引中的任何一个，“the item is not presented”或者“the item is presented at index i”。

现在，假设允许您的算法使用数组的唯一方法是通过询问以下形式的问题：“项是否大于或等于索引i中的项？”对于i的一些选择，让我们想象一下，你问一个形式为k总时间的问题。然后，有2^k种可能的方式可以使比较恢复。要了解原因，有两个选项来说明第一个比较的方式（“是”或“否”）。第二次比较有两个选项（“是”或“否”），第三次比较有两个选项。所有这些2相乘得到2^k。

我们现在有两个制约因素：

1. 任何正确的算法都必须能够返回n+1个不同选项中的一个。
2. 对于k个比较，这些比较有2^k种可能的方法。

这意味着我们必须有n+1≤2^k，因为否则搜索算法没有足够的可能结果来覆盖所有n+1个可能结果。取两边的对数基数为2给出lg(n+1)≤k，因此进行比较的次数必须为？（log n）。

换种说法--如果您的算法进行的查询太少，那么就没有足够的方法进行比较，以确保产生每个可能的选项。

需要注意的是，有一些算法，在某些假设的前提下，可以比这更好。例如，插值搜索可以在预期时间O（log log n）内找到排序数组中的项，前提是数据看起来像线性函数。然而，最坏情况的运行时仍然是？（log n)，因为这是一个基于比较的算法。更好的性能来自对数据分布的附加假设。

融合树可以在时间O（log n/log w）内执行搜索，其中w是机器字大小，前提是值是适合于单个机器字的整数。这可以改进到O（sqrt（log n/log log n））的惊人运行时。众所周知，如果n个值都适合于一个机器字，那么前面的下界说您不能比（非常不寻常的运行时）O（min{log w/log log w,sqrt（log n/log log n）}）做得更好，其中w是机器字大小。这些算法通过在单个机器词上使用创造性操作并行地进行多次比较，从而超过？（log n）下限。