Резкая концентрация для выбора с помощью случайного разделения?

Обычный простой алгоритм для нахождения медианного элемента в массиве из чисел:$A$$n$

• Пример элементов из с заменой на$n^{3/4}$$A$$B$
• Сортируйте и найдите элементы ранга и из| Б | ± $B$ lr$|B|\pm \sqrt{n}$$l$$r$$B$
• Убедитесь , что и находятся на противоположных сторонах средней части и что существует не более элементами в А между л и г для некоторых соответствующих постоянная С > 0 . Сбой, если этого не произойдет.r A C $l$$r$$A$$C\sqrt{n}$$A$$l$$r$$C > 0$
• В противном случае найдите медиану, отсортировав элементы $A$ между $l$ и $r$

Нетрудно видеть, что это происходит за линейное время и что это происходит с большой вероятностью. (Все плохие события - большие отклонения от ожидания бинома.)

Альтернативный алгоритм для той же задачи, который более естественно преподавать учащимся, которые видели быструю сортировку, описан здесь: Рандомизированный отбор

Также легко увидеть, что у этого есть линейное ожидаемое время выполнения: скажем, что «раунд» - это последовательность рекурсивных вызовов, которая заканчивается, когда кто-то дает разбиение 1 / 4-3 / 4, а затем наблюдаем, что ожидаемая длина раунд не более 2. (В первом тираже раунда вероятность получения хорошего разделения равна 1/2, а затем после фактического увеличения, как было описано в алгоритме, поэтому в длине раунда преобладает геометрическая случайная величина.)

Итак, теперь вопрос:

Можно ли показать, что рандомизированный отбор проходит в линейное время с высокой вероятностью?

У нас есть раундов, и каждый раунд имеет длину не менее k с вероятностью не более 2 - k + 1 , поэтому при объединении получается, что время выполнения равно O ( n log log n ) с вероятностью 1 - 1 / O ( журнал N ) .$O(\log n)$$k$$2^{-k+1}$$O(n\log\log n)$$1-1/O(\log n)$

Это отчасти неудовлетворительно, но на самом ли деле это правда?

Это неправда, что алгоритм работает в линейное время с высокой вероятностью. Принимая во внимание только первый раунд, время работы составляет не менее раз в G ( 1 / 2 ) случайная величина. Пусть p ( n ) ⟶ 0 - допустимая вероятность отказа. Так как Pr [ G ( 1 / 2 ) ≥ войти 2 р ( п ) - 1 ] = р ( п ) , время работы, по крайней мере$\Theta(n)$$G(1/2)$$p(n) \longrightarrow 0$$\Pr[G(1/2) \geq \log_2 p(n)^{-1}] = p(n)$$\Omega(n \log_2 p(n)^{-1}) = \omega(n)$

$G(1/2)$

$n$