Gallop搜索时间复杂度？

Question

Gallop搜索用于搜索排序列表中的元素.您开始在索引0处获取元素,然后在索引1,2,4,8,1等处获取元素,直到您超过目标,然后再次搜索刚刚找到的范围.

这个时间的复杂性是多少？在我看来,它是某种对数时间复杂度,但我无法弄清楚是什么.

Answer 1

（请参阅下面我的编辑）

让我们看看最坏情况的行为。搜索从 0, 1, 2, 4, 8... 继续，假设对于某些 k >= 0，n 是 2^k。在最坏的情况下，我们可能最终会搜索到 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 的二次方。它可能不是最紧的界限，但它是一个很好的上限。

编辑：我错了。我从字面上理解了此处给出的驰骋搜索的定义，而没有点击链接。该链接说，一旦我们超出了范围，我们就会在之前的时间间隔中进行二分搜索。超出目标需要 log(n) 时间，在排序区间内进行二分搜索需要 log(n) 时间。这使其成为 O(log(n)) 算法。感谢Sumudu Fernando在评论中指出这一点。我很感激。