сложность рандомизированного алгоритма поиска

Question

Рассмотрим следующий рандомизированный алгоритм поиска на отсортированном массиве a длины n (в порядке возрастания). x может быть любым элементом массива.

size_t randomized_search(value_t a[], size_t n, value_t x) 
    size_t l = 0; 
    size_t r = n - 1; 
    while (true) { 
     size_t j = rand_between(l, r); 
     if (a[j] == x) return j; 
     if (a[j] < x) l = j + 1; 
     if (a[j] > x) r = j - 1; 
    } 
} 

Каково значение ожидание Big Theta complexity (ограничено как ниже, так и выше) этой функции, когда x выбран случайным образом из a?

Хотя это кажется log(n), я провел эксперимент с подсчета команд, и выяснилось, что результат растет немного быстрее, чем log(n) (по моим данным, даже (log(n))^1.1 лучше подходят результат).

Кто-то сказал мне, что этот алгоритм имеет точные большая сложность тета (так очевидно log(n)^1.1 не ответ). Итак, не могли бы вы рассказать о временной сложности и своем подходе, чтобы доказать это? Благодарю.

---

Update: данные из моего эксперимента

log(n) подходят результат по Mathematica:

log(n)^1.1 подходят результат:

Answer 1

Если вы хотите переключиться на подсчет трехсторонних сравнений, я могу сказать вам точную сложность.

Предположим, что ключ находится в положении i, и я хочу знать ожидаемое количество сравнений с положением j. Я утверждаю, что положение j проверяется, если и только если это первая позиция между i и j включительно для проверки. Поскольку элемент поворота выбирается равномерно случайным образом каждый раз, это происходит с вероятностью 1/(| i - j | + 1).

Суммарная сложность является ожидание в течение я < - {1, ..., п} из sum_ {j = 1}^N 1/(| I - J | + 1), который является

sum_{i=1}^n 1/n sum_{j=1}^n 1/(|i - j| + 1) 
= 1/n sum_{i=1}^n (sum_{j=1}^i 1/(i - j + 1) + sum_{j=i+1}^n 1/(j - i + 1)) 
= 1/n sum_{i=1}^n (H(i) + H(n + 1 - i) - 1) 
= 1/n sum_{i=1}^n H(i) + 1/n sum_{i=1}^n H(n + 1 - i) - 1 
= 1/n sum_{i=1}^n H(i) + 1/n sum_{k=1}^n H(k) - 1 (k = n + 1 - i) 
= 2 H(n + 1) - 3 + 2 H(n + 1)/n - 2/n 
= 2 H(n + 1) - 3 + O(log n/n) 
= 2 log n + O(1) 
= Theta(log n). 

(журнал означает натуральный журнал здесь.) Обратите внимание на -3 в условиях низкого порядка. Это делает его похожим на то, что число сравнений растет быстрее, чем логарифмическое в начале, но асимптотическое поведение диктует его уровень. Попробуйте исключить небольшие n и переделать свои кривые.

Answer 2

Предполагая, что rand_between для реализации выборки из равномерного распределения вероятности в постоянное время, ожидаемое время работы этого алгоритма составляет Θ (lg n). Неофициальный эскиз доказательства: ожидаемое значение rand_between(l, r) - (l+r)/2, середина между ними. Таким образом, каждая итерация, как ожидается, пропускает половину массива (при условии, что размер равен двум), как и одна итерация бинарного поиска.

Более формально, заимствование из анализа quickselect, заметим, что, когда вы выбираете случайную середину, половину времени он будет находиться в диапазоне от ¼ п и ¾ п. Ни левый, ни правый подрамник не имеет более ¾ n элементов. Другая половина времени не имеет более n элементов (очевидно). Это приводит к рекуррентным соотношением

T(n) = ½T(¾n) + ½T(n) + f(n) 

, где F (п) является объем работы на каждой итерации. Вычитание ½T (п) с обеих сторон, то удвоение обеих сторон, мы имеем

½T(n) = ½T(¾n) + f(n) 
T(n) = T(¾n) + 2f(n) 

Теперь, так как 2f (п) = Θ (1) = Θ (п ᶜ log⁰ п), где с = журнал (1) = 0, то по основной теореме, что Т (п) = Θ (п ⁰ Л.Г. п) = Θ (LG п).