怎么可能做的二进制搜索在双向链表中的O（n）的时间？ [英] How is it possible to do binary search on a doubly-linked list in O(n) time?

问题描述

我听说它可以实现在一个双向链表在O（n）时间二进制搜索。访问的双向链表的随机元素需要O（n）的时间，和二进制搜索访问O（log n）的不同元素，所以不应该在运行时为O（n log n）的呢？

解决方案

这在技术上是正确的说，在一个双向链表二进制搜索的运行时间是O（n log n）的，但这不是一个紧的上界。使用一个稍微好一点的执行二进制搜索的和更巧妙的分析，有可能得到二进制搜索的时间为O（n）的运行。

后面二进制搜索的基本思想是：

• 如果该列表为空，所搜索的不存在的元素。
• 否则：
  • 看看中间元素。
  • 如果它有问题的元素相匹配，返回它。
  • 如果它比有问题的元素，丢弃列表的后一半。
  • 如果它比有问题的元件较小，放弃前面的列表的一半。

这是一个双向链表一个天真的执行二进制搜索会通过计算索引来查找在每次迭代（就像在阵的情况下）的工作，然后开始在列表和扫描的前访问每一个转发步骤的适当数量。这的确是很慢的。如果搜索是在阵列的最末端的元件时，指数抬头将是n / 2个和3n / 4，7N / 8等总结在最坏的情况下进行的工作，我们得到

  

N / 2 + 3N / 4 + 7N / 8 + 15N / 16 + ...（西塔（log n）的条款）

     

＆GE; N / 2 + N / 2 + ... + N / 2（西塔（log n）的条款）

     

=西塔（N日志N）

和

  

N / 2 + 3N / 4 + 7N / 8 + 15N / 16 + ...（西塔（log n）的条款）

     

＆乐; N + N + ... + N（西塔（log n）的条款）

     

=西塔（N日志N）

因此​​，对于这种算法的最坏情况下的时间复杂度是＆西塔;（正log n）的

通过更巧妙的用我们的方法（log n）的;

不过，我们可以通过与西塔的一个因素加速此。究其原因，previous算法是缓慢的是，每一个我们需要查找一个元素时，我们开始从数组的开始搜索。然而，我们并不需要这样做。细算起来，中间元素中的第一次，我们已经在阵列的中间，我们知道我们将要进行下一次查找会无论是在位置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 + ...）

     

＆乐; ñ

此如下一个事实，即无限几何级数的总和的1/2 + 1/4 + 1/8 + ...为1。因此，在最坏的情况下完成的仅＆西塔总工作;（n）的，这比＆西塔好得多;从之前（正log n）的最坏情况的

最后一个细节：？为什么你会永远这样做的毕竟，它已经需要O（n）的时间来搜索一个双向链表的一个元素。这种方法的一个主要优点是，即使在运行时是O（n），我们只落得做O（log n）的总的比较（占二进制搜索的步骤之一）。这意味着，如果比较昂贵，我们最终可能会少做工作，用不是做一个普通的线性搜索二进制搜索，因为O（n）的来自所做的工作走在列表，而不是做做比较的工作。

I've heard that it's possible to implement binary search over a doubly-linked list in O(n) time. Accessing a random element of a doubly-linked list takes O(n) time, and binary search accesses O(log n) different elements, so shouldn't the runtime be O(n log n) instead?

解决方案

It's technically correct to say that the runtime of binary search on a doubly-linked list is O(n log n), but that's not a tight upper bound. Using a slightly better implementation of binary search and a more clever analysis, it's possible to get binary search to run in time O(n).

The basic idea behind binary search is the following:

• If the list is empty, the element being searched for doesn't exist.
• Otherwise:
  • Look at the middle element.
  • If it matches the element in question, return it.
  • If it's bigger than the element in question, discard the back half of the list.
  • If it's smaller than the element in question, discard the front half of the list.

A naive implementation of binary search on a doubly-linked list would work by computing the indices to look up on each iteration (just like in the array case), then access each one by starting at the front of the list and scanning forward the appropriate number of steps. This is indeed very slow. If the element being searched for is at the very end of the array, the indices looked up would be n/2, 3n/4, 7n/8, etc. Summing up the work done in the worst case, we get

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

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

= Θ(n log n)

and

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

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

= Θ(n log n)

Therefore, the worst-case time complexity for this algorithm is Θ(n log n).

However, we can speed this up by a factor of Θ(log n) by being more clever with our approach. The reason the previous algorithm is slow is that every time we need to look up an element, we start the search from the beginning of the array. However, we don't need to do this. After looking up the middle element the first time, we're already in the middle of the array, and we know that the next lookup we're going to make will be either at position n / 4 or 3n / 4, which is only distance n / 4 from where we left off (compared to n / 4 or 3n / 4 if we start from the beginning of the array). What if we just trekked out from our stopping position (n / 2) to the next position, rather than restarting at the front of the list?

Here's our new algorithm. Begin by scanning to the middle of the array, which requires n / 2 steps. Then, determine whether to visit the element at the middle of the first half of the array or the middle of the second half of the array. Reaching there from position n / 2 only requires n / 4 total steps. From there, going to the midpoint of the quarter of the array containing the element takes only n / 8 steps, and going from there to the midpoint of the eighth of the array containing the element takes only n / 16 steps, etc. This means that the total number of steps made is given by

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

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

≤ n

This follows from the fact that the sum of the infinite geometric series 1/2 + 1/4 + 1/8 + ... is 1. Therefore, the total work done in the worst case only Θ(n), which is much better than the Θ(n log n) worst case from before.

One last detail: why would you ever do this? After all, it already takes O(n) time to search a doubly-linked list for an element. One major advantage of this approach is that even though the runtime is O(n), we only end up doing O(log n) total comparisons (one per step of the binary search). This means that if comparisons are expensive, we might end up doing less work using a binary search than doing a normal linear search, since the O(n) comes from the work done walking the list rather than the work done making comparisons.

这篇关于怎么可能做的二进制搜索在双向链表中的O（n）的时间？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！