![]() |
1
33
从技术上讲,双链表上二进制搜索的运行时间是O(n-logn)是正确的,但这不是一个严格的上限。使用稍微好一点的二进制搜索实现和更聪明的分析,可以使二进制搜索在时间O(n)内运行。 二进制搜索背后的基本思想如下:
在双链表上进行二进制搜索的一个简单实现是通过计算索引来查找每个迭代(就像在数组的情况下一样),然后从列表的前面开始并向前扫描适当数量的步骤来访问每个迭代。这确实非常缓慢。如果要搜索的元素位于数组的最末端,则查找的索引将是n/2、3n/4、7n/8等。将在最坏情况下所做的工作相加,我们得到
和
因此,该算法的最坏情况时间复杂度为Θ(n-logn)。 然而,我们可以通过更巧妙的方法将速度提高一倍,即θ(logn)。前面的算法之所以慢,是因为每次我们需要查找元素时,我们都从数组的开头开始搜索。然而,我们不需要这样做。第一次查找中间的元素后,我们已经在数组的中间了,我们知道下一次查找将在位置n/4或3n/4处,这是我们离开的位置的距离n/4(相比之下,如果我们从数组的开头开始查找,则为n/4或者3n/4)。如果我们只是从停止位置(n/2)跋涉到下一个位置,而不是在列表的前面重新开始,会怎么样? 这是我们的新算法。首先扫描到阵列的中间,这需要n/2个步骤。然后,确定是访问阵列的前半部分的中间还是访问阵列的后半部分的中间的元素。从n/2位置到达那里只需要总共n/4个步骤。从那里到包含元素的数组的四分之一的中点只需n/8步,从那里到含有元素的数组第八个的中点只需要n/16步,等等。这意味着所做的步骤总数由下式给出
这源于无限几何级数1/2+1/4+1/8+的和。。。为1。因此,在最坏情况下所做的总功只有θ(n),这比以前的θ(n log n)最坏情况要好得多。 最后一个细节: 你为什么要这样做? 毕竟,在双链表中搜索一个元素已经花费了O(n)时间。这种方法的一个主要优点是,即使运行时是O(n),我们最终也只能进行O(logn)个总比较(二进制搜索的每一步一个)。这意味着,如果比较代价高昂,我们最终可能会使用二进制搜索比使用普通线性搜索做更少的工作,因为O(n)来自于在列表中遍历所做的工作,而不是进行比较的工作。 |
![]() |
Bala Ji · 以下BFS的实施效率如何? 5 月前 |
![]() |
Bioinfotec · 如何在R中将两个嵌套列表合并为一个列表? 6 月前 |
![]() |
b39b332d · 使用C++标准库实现高效间隔存储 10 月前 |
![]() |
ep84 · Python中处理扩展线性序列的快速(最快)方法 11 月前 |
![]() |
Gerry · python中高效的Merge排序实现 1 年前 |
![]() |
Noel · C#通过引用返回结构导致复制 1 年前 |