14

我听说可以在 O(n) 时间内在双向链表上实现二进制搜索。访问双向链表的随机元素需要 O(n) 时间，而二进制搜索访问 O(log n) 不同的元素，所以运行时不应该是 O(n log n) 吗？

4

1 回答 1

33

说双向链表上的二进制搜索的运行时间是 O(n log n) 从技术上讲是正确的，但这不是一个严格的上限。使用更好的二分搜索实现和更聪明的分析，可以让二分搜索在 O(n) 时间内运行。

二分查找的基本思想如下：

  • 如果列表为空，则正在搜索的元素不存在。
  • 否则：
    • 看中间元素。
    • 如果它与有问题的元素匹配，则返回它。
    • 如果它大于相关元素，则丢弃列表的后半部分。
    • 如果它小于相关元素，则丢弃列表的前半部分。

在双向链表上的二进制搜索的简单实现将通过计算索引以在每次迭代中查找（就像在数组情况下一样），然后通过从列表的前面开始并向前扫描适当的步数。这确实很慢。如果要搜索的元素位于数组的最后，则查找的索引将是 n/2、3n/4、7n/8 等。总结在最坏情况下所做的工作，我们得到

n / 2 + 3n/4 + 7n/8 + 15n/16 + ... (Θ(log n) 项)

≥ n / 2 + n / 2 + ... + n / 2 (Θ(log n) 项)

= Θ(n log n)

和

n / 2 + 3n/4 + 7n/8 + 15n/16 + ... (Θ(log n) 项)

≤ n + n + ... + n (Θ(log n) 项)

= Θ(n log n)

因此，该算法的最坏情况时间复杂度为 Θ(n log n)。

然而，我们可以通过更聪明地使用我们的方法来加速 Θ(log n) 的速度。前面算法慢的原因是每次我们需要查找一个元素时，我们都是从数组的开头开始查找。但是，我们不需要这样做。在第一次查找中间元素后，我们已经在数组中间，我们知道我们要进行的下一次查找将在位置 n / 4 或 3n / 4，这只是距离我们离开的地方 n / 4 （与 n / 4 或 3n / 4 相比，如果我们从数组的开头开始）。如果我们只是从停止位置 (n / 2) 移动到下一个位置，而不是从列表的前面重新开始呢？

这是我们的新算法。首先扫描到阵列的中间，这需要 n / 2 步。然后，判断是访问数组前半部分中间的元素还是数组后半部分中间的元素。从位置 n / 2 到达那里只需要 n / 4 步。从那里到包含元素的数组的四分之一的中点只需要 n / 8 步，从那里到包含元素的数组的八分之一的中点只需要 n / 16 步，依此类推。这意味着总步数由下式给出

n / 2 + n / 4 + n / 8 + n / 16 + ...

= n (1/2 + 1/4 + 1/8 + ...)

≤ n

这是因为无限几何级数 1/2 + 1/4 + 1/8 + ... 之和为 1。因此，在最坏情况下完成的总功只有 Θ(n)，这要大得多比之前的 Θ(n log n) 最坏情况要好。

最后一个细节：你为什么要这样做？毕竟，在双向链表中搜索元素已经花费了 O(n) 时间。这种方法的一个主要优点是，即使运行时间是 O(n)，我们最终也只会进行 O(log n) 的总比较（二进制搜索的每一步）。这意味着如果比较代价高昂，我们可能最终使用二分搜索比进行正常线性搜索做的工作更少，因为 O(n) 来自遍历列表完成的工作，而不是进行比较完成的工作。

于 2013-10-23T23:51:19.380 回答