为什么不可能比 O(log n) 更快地在排序数组中找到指定值？

Question

我对计算机科学很陌生。在讲座结束时，我的 AP 计算机科学老师提到在排序数组中查找指定值的比较模型是big omega (log n) ie ?(log n)，据我所知，这意味着它是不可能完成的这个任务比O(log n)快。为什么是这样？

Answer 1

假设您有一个包含 n 个项目的数组。如果您在此数组中执行查找，则该查找可以返回 n + 1 个值之一：对于 n 个索引中的任何一个，“该项目不存在”或“该项目存在于索引 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(1) 查找，而其他哈希表（例如布谷鸟散列）提供最坏情况的 O(1) 查找。

在比较模型之外，有些算法根据某些假设，预期运行时间低于 O(log n)。例如，插值搜索可以在预期时间 O(log 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) 下限。

Answer 2

首先，在谈论 Big-O 复杂性时要小心使用“更快”这个词，正如问题标题中所做的那样。Big-O 没有说明算法的速度有多快。Big-O 仅说明当某些变量 N 发生变化时执行时间如何变化。例子：

O(1) algorithm   : Doubling N will not change execution time
O(N) algorithm   : Doubling N will double execution time (1 + 1 = 2) 
O(N^2) algorithm : Doubling N will quadruple execution time (2 * 2 = 4)

另请注意，对于某些 N 值，O(N^2) 算法可能比 O(N) 算法快。Big-O 对此一无所知。我们只能说，如果我们不断增加 N，那么 O(N) 算法迟早会比 O(N^2) 算法快。但是 Big-O 并没有说明 N 的值是多少。它可以是 N=1, N=10, N=100, ... 所以在将 Big-O 复杂性“转换”为“快速”时要小心。

Big-O 计算为您需要执行一些基本操作（O(1) 操作）的次数作为变量 N 的函数。此外，Big-O（通常）考虑最坏的情况。

对于普通数组，我们可以执行的唯一基本操作是i在 1..N 范围内的某个索引处查找值

在排序数组中，返回值可用于告诉我们三件事（有关例外情况，请参见后面的段落）：

1. 该值是否小于我们正在搜索的值
2. 该值是否大于我们正在搜索的值
3. 该值是否等于我们正在搜索的值

现在请记住，Big-O 是关于最坏情况的情景。所以数字 3 不会发生，除非我们在一个只有一个数组元素的范围内查找。所以暂时忘掉第 3 点吧。

因为数组是排序的，所以相关的答案可以翻译成

1. 搜索值在范围 1 .. i
2. 搜索值在i+1 .. N范围内

现在的问题是：如何i为第一次查找选择最佳值？

由于 Big-O 是最坏情况计算，因此我们将始终使用两个范围中最大的一个进行下一步。为了使最大范围尽可能小，我们需要使两个范围的大小相同。为此，我们需要i等于 N/2。这简直是​​我们利用从查找中获得的知识所能做的最好的事情。

通过这样做，我们有

1. 搜索值在 1 .. N/2 范围内
2. 搜索值在 N/2+1 .. N 范围内

因此，在下一步中，我们需要查看包含 N/2 个元素的范围。

现在再次应用相同的（即i= N/2/2）进行下一次搜索以减少到 N/4 元素。再做一次以获得 N/8 个元素等等......

重复此操作，直到范围中有 1 个元素 - 然后我们就有了解决方案（上面的数字 3）。

所以每次查找都会将范围缩小到原始大小的一半。并且k查找会将范围减少2^k。我们的目标是使范围大小为 1，因此我们需要解决：

N / 2^k = 1 <=> N = 2^K <=> K = log ₂ (N)

因此，假设我们从查找中只能知道我们的搜索值是在查找位置的左侧还是右侧，并且根据 Big-O 是最坏情况计算的事实，我们可以看到搜索在排序数组中不能比 log(N) 复杂度更好。

以上涵盖了一般数组，但请注意，对于某些数组，假设可能不成立。有时，算法可能会从 index 处的查找值中提取更多信息i。例如，如果我们对数组中值的分布有所了解，而我们的搜索值与查找值相差甚远，则算法可能会受益于在下一次查找中执行其他操作而不是在 N 处进行下一次查找/2，从而更有效率。

Answer 3

如果您不知道有关密钥分布的初步信息，实际上，您的搜索是 O(log(n))，因为每次比较您提取 1 位 if 信息，并将搜索区域缩小两次。但是，对于实际情况，您可以更快地在排序数组中进行搜索。例如，参见插值搜索，它只是 O(log(log(n)))。