Галоп Поиск сложности времени? - PullRequest
Новая
       5

Галоп Поиск сложности времени?

5 голосов
/ 10 марта 2011

Поиск галопом - для поиска элемента в отсортированном списке.Вы начинаете брать элемент с индекса 0, затем с индекса 1, 2, 4, 8, 16 и т. Д. До тех пор, пока не достигнете цели, а затем снова выполните поиск в только что найденном диапазоне.

Что такоевременная сложность этого?Мне кажется, это какая-то сложность логарифмического времени, но я не могу понять, что.

1 Ответ

3 голосов
/ 10 марта 2011

(см. Мой РЕДАКТИРОВАТЬ ниже)

Давайте посмотрим на худшее поведение.поиск продолжается с 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 за то, что он указал на это в комментариях.Я ценю это.

...