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

#algorithm #recursion #big-o #big-theta

#алгоритм #рекурсия #big-o #big-theta

Вопрос:

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

Вот что я получил для T (n)

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

Тем не менее, я понятия не имею, как получить жесткую привязку.

1. Наихудший случай — O(n), если генератор случайных чисел всегда выбирает 1 или n.

2. @MarkRansom … что происходит с вероятностью 2 / факториал(n). Другими словами, никакого заметного влияния на время вычислений при крошечных значениях n, гораздо менее вероятно, чем попадание метеорита при n> 10, и «никогда не произойдет в этой вселенной» при n> 20.

3. @pjs Я говорил о наихудшем случае в математическом смысле, будь прокляты вероятности. Это сильно отличается от практической дискуссии. Поскольку вопрос касался «жесткой привязки», я подумал, что это может иметь какое-то отношение.

4. @MarkRansom Поскольку вопрос касался «жесткой привязки к ожидаемому времени выполнения», сосредоточение внимания на наихудшем случае не имеет никакого значения. Ожидаемое значение — это вероятностная концепция, которая взвешивает результаты с учетом их вероятности наступления. Ваш наихудший случай практически не влияет на время выполнения, где он имеет заметную вероятность возникновения, и в ожидании очень быстро приближается к нулевому воздействию.

5. Ой, сделайте эту вероятность (2 ^ n) / факториал (n). Он по-прежнему удивительно быстро сходится к нулю, например, 4.3E-13 для n = 20, 4E-24 для n = 30.

Ответ №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(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)

Число гармоник

граница H(n)