Gallop搜索时间复杂度是多少？

Question

Gallop搜索时间复杂度是多少？

time-complexity

6

Gallop search 用于在排序列表中搜索元素。你从索引0开始，然后是索引1、2、4、8、16等，直到你超过目标，然后在刚才找到的范围内再次搜索。

这个算法的时间复杂度是什么？它似乎是某种对数时间复杂度，但我无法确定具体是什么。

- user541686

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Srikanth · Accepted Answer

请参见下面我的编辑

让我们先看最坏情况。搜索从0、1、2、4、8...继续。假设n是2 ^ k，其中k> = 0。在最坏情况下，我们可能会一直搜索到2 ^ k，然后意识到我们超过了目标。现在我们知道目标可以在2 ^（k-1）和2 ^ k之间。该范围内的元素数量为2 ^（k-1）（考虑一下）。到目前为止，我们已经检查的元素数量为O（k），即O（logn）。以下递归总结了它。

T(n) = T(n/2) + O(logn) 
     = T(n/4) + c1log(n/2) + c2logn ((all logs are base 2.))
     .
     .
     .
     .
     = O((logn)^2)

所以，该算法的最坏复杂度是logn的二次方。这可能不是最紧密的限制，但它是一个很好的上限。

编辑：我错了。我字面上采用了这里给出的gallop search的定义，而没有按照链接进行操作。链接说，一旦我们超过了目标，我们就在前一个间隔中进行二分查找。超过目标需要log(n)的时间，在排序的间隔中进行二分查找也需要log(n)的时间。这使得它成为O(log(n))算法。感谢Sumudu Fernando在评论中指出。我非常感激。