time-complexity - Gallop 搜索时间复杂度？

Question

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

这个时间复杂度是多少？在我看来，这是某种对数时间复杂度，但我不知道是什么。

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 的二次方。它可能不是最严格的界限，但它是一个很好的上限。

编辑:我错了。我在没有遵循链接的情况下从字面上理解了此处给出的 gallop 搜索的定义。链接说，一旦我们超调，我们就会在前一个时间间隔内进行二分搜索。超过目标需要 log(n) 时间，在排序间隔中进行二分搜索需要 log(n) 时间。这使它成为 O(log(n)) 算法。感谢 Sumudu Fernando在评论中指出。我很感激。