Время выполнения рандомизированного двоичного поиска

Question

Рассмотрим следующий глупый рандомизированный вариант бинарного поиска. Вам задан отсортированный массив А из n целых чисел и целого числа v, которое вы ищете, выбирается равномерно случайным образом из A. Затем вместо сравнения v со значением в середине массива рандомизированный двоичный поиск вариант выбирает случайное число r от 1 до n и сравнивает v с A [r]. В зависимости от того, больше или меньше v, этот процесс повторяется рекурсивно в левой части массива или в правой поддиапазоне до тех пор, пока не будет найдено местоположение v. Докажите ограниченную привязку ожидаемого времени работы этого алгоритма.

Вот что я для Т (п)

T(n) = T(n-r) + T(r) + Θ(1)

Однако, я понятия не имею, как получить точную оценку.

Answer 1

Ваша формулировка T (n) не совсем корректна. Фактически,

Давайте попробуем рассмотреть все случаи. Когда мы уменьшаем размер проблемы, разбивая массив на любую случайную точку, уменьшенная субамба будет иметь размер от 1 до n с равномерной вероятностью. Следовательно, с вероятностью 1/n пространство поиска становится r. Так ожидается, время работы становится

T(n) = sum (T(r)*Pr(search space becomes r)) + O(1) = sum (T(r))/n + O(1)

Который дает,

T(n) = average(T(r)) + O(1)

Пусть ожидаются временной сложность случайного двоичного рода будет Т (п).

T(n) = [ T(1)+T(2)+...+T(n)]/n + 1 
n*T(n) = T(1)+T(2)+...+T(n) + n 
(n-1)*T(n-1) = T(1)+T(2)+...+T(n-1) + n-1  [substituiting n by n-1] 
n*T(n) - (n-1)*T(n-1) = T(n) + 1 
(n-1)*T(n) - (n-1)*T(n-1) = 1 
(n-1)*T(n) = (n-1)*T(n-1) + 1 
T(n) = 1/(n-1) + T(n-1) 
T(n) = 1/(n-1) + 1/(n-2) + T(n-2)    [ T(n-1) = T(n-2) + 1/(n-2) ] 
... 
T(n) = 1 + 1/2 + 1/3 + ... + 1/(n-1) = H(n-1) < H(n) = O(log n) 
[ H(n) = reciprocal sum of first n natural numbers ] 

так, T(n) = O(log n)

Harmonic number

bound of H(n)