tem*_*def 14 algorithm big-o binary-search data-structures doubly-linked-list
我听说可以在O(n)时间内在双向链表上实现二进制搜索.访问双向链表的随机元素需要O(n)时间,二进制搜索访问O(log n)个不同的元素,所以运算符不应该是O(n log n)吗？
tem*_*def 29
从技术角度来说,双链表上的二进制搜索的运行时间是O(n log n),但这不是一个紧密的上限.使用稍微更好的二进制搜索实现和更聪明的分析,可以使二进制搜索在时间O(n)中运行.
二进制搜索背后的基本思想如下:
在双向链接列表上进行二进制搜索的简单实现可以通过计算索引来查找每次迭代(就像在数组中一样),然后通过从列表的前面开始并向前扫描相应的来访问每个迭代.步数.这确实很慢.如果被搜索的元素位于数组的最末端,则查找的索引将是n/2,3 n/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)来自完成列表的工作,而不是完成比较的工作.