Рандомизированный выбор

Question

Алгоритм рандомизированного отбора является следующим:

Ввод: массив $ a $ $ n $ (различные, для простоты) номера и число $ k in [n] $

Вывод: «Элемент" ранга $ k $ "$ a $ (т.е. тот, который находится в позиции $ k $, если $ a $ была отсортирована)

Метод:

• Если есть один элемент в $ A $, верните его
• Выберите элемент $ p $ («pivot»), равномерно случайно
• Вычислить наборы $ l = {a in a: a <p } $ и $ r = {a in a: a> p } $
• Если $ | l | ge k $, вернуть звание $ k $ element of $ l $.
• В противном случае вернуть звание $ k - | l | $ element of $ r $

Мне задали следующий вопрос:

Предположим, что $ k = n/2 $, так что вы ищете медиану, и пусть $ alpha in (1/2,1) $ будет постоянной. Какова вероятность того, что при первом рекурсивном вызове набор, содержащий медиана, имеет размер максимум $ alpha n $?

Мне сказали, что ответ составляет $ 2 alpha - 1 $, с оправданием «Выбранная стержня должна лежать от 1 доллара alpha $ и $ alpha $

Почему? Как $ alpha in (0,5, 1) $, любой элемент выбран в качестве pivot, либо больше, либо меньше, чем более половины исходных элементов. Медиана всегда лежит в более крупном субраре, потому что элементы в разделенном субраре всегда меньше, чем стержень.

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

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

Пример:

3 4 5 8 7 9 2 1 6 10

Медиана 5.

Предполагается, что выбранная шарнир - 2. Так что после первой итерации он становится:

1 2 .... Большая часть ....

Только 1 а также 2 поменяются после первой итерации. Номер 5 (медиана) все еще находится в первой большей половине (добравшись до pivot 2). Дело в том, что медиана всегда лежит на большей половине, как у него может быть шанс остаться в меньшем субраре?

Answer 1

Предположим, в вашем массиве есть элементы $ $. Как вы отметили, медиана всегда в большей части после первого раздела. Большая часть имеет размер не более $ alpha n $, если меньшая часть имеет размер как минимум $ (1- alpha) n $. Это происходит, когда вы выбираете поворот, который не является одним из самых маленьких или крупнейших элементов $ (1- alpha) n $. Поскольку $ alpha> 1/2 $, вы знаете, что это непересеченные наборы, поэтому вероятность попадания одного из плохих поворотов составляет всего 2 доллара США - 2 Альфа $, а $ 1- 2 + 2 Alpha = 2 Alpha - 1 $.