快速搜索時間複雜度？

Question

Gallop search用於搜索排序列表中的元素。你開始在索引0獲取一個元素，然後在索引1,2,4,8,16等，直到你超出你的目標，然後再次搜索你剛發現的範圍。

什麼是這個時間複雜度？在我看來，這是一種對數時間複雜度，但我無法弄清楚什麼。

Answer 1

（請參閱下面我的編輯）

讓我們看看最壞情況下的行爲。搜索繼續從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的二次方。它可能不是最緊密的界限，但它是一個很好的上限。

編輯：我錯了。我已經在這裏給出了這裏給出的馳騁搜索的定義，而沒有遵循鏈接。鏈接說，一旦我們超調，我們在前一個時間間隔進行二分搜索。超過目標和log（n）時間需要log（n）時間才能在排序的間隔中執行二進制搜索。這使它成爲O（log（n））算法。感謝Sumudu Fernando在評論中指出。我很感激。