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

14

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

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

Выходные данные: « элемент ранга » в A (т. Е. Элемент в позиции k, если A был отсортирован)kAkA

Метод:

  • Если в есть один элемент , верните егоA
  • Выберите элемент («стержень») равномерно случайным образомp
  • Вычислить множества и R = { a A : a > p }L={aA:a<p}R={aA:a>p}
  • Если , возвращает ранг K элемент L .|L|kkL
  • В противном случае вернуть ранг элемент Rk|L|R

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

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

Мне сказали, что ответом является , с обоснованием «Выбранная ось должна лежать между 1 - α и α, умноженной на исходный массив»2α11αα

Почему? При любой элемент, выбранный в качестве точки поворота, либо больше, либо меньше, чем половина исходных элементов. Медиана всегда лежит в большем подмассиве, потому что элементы в секционированном подмассиве всегда меньше, чем стержень.α(0.5,1)

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

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

Пример:

3 4 5 8 7 9 2 1 6 10

Медиана 5.

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

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

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

Амуму
источник
Мы не сидели на вашей лекции, поэтому, пожалуйста, объясните метод.
Рафаэль
Не зная, какой точный алгоритм вы говорите, ваш вопрос не читается. Вы, кажется, используете в нескольких мощностях; Я пытался редактировать, но не уверен, что понял смысл. Пожалуйста, измените, чтобы вопрос был ясен. Голосование, чтобы закрыть до тех пор. .5
Рафаэль
Это алгоритм выбора с использованием рандомизированного метода, а не детерминированного метода.
Amumu
Есть много способов выбрать элемент случайным образом.
Рафаэль
2
@Amumu: я отредактировал его, чтобы описать алгоритм. На таком форуме не все поймут, о чем вы говорите, и существует совершенно другой рандомизированный подход к выбору, который легче анализировать.
Луи

Ответы:

12

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

Луис
источник
Спасибо за ответ. У меня все еще есть несколько неясных вещей. Итак, какое отношение α> 1/2 имеет отношение к непересекающимся множествам? Я думал, что когда у нас всегда есть непересекающиеся множества с этим методом, независимо от размера подрешетки.
Amumu
Потому что это делает , так что ( 1 - & alpha ; ) п < п - ( 1 - & alpha ; ) п . 1α<1/2(1α)n<n(1α)n
Луи
И еще одна вещь: какое отношение к этому имеет плохой / хороший пивот? Насколько я знаю, хороший круг обычно находится в диапазоне 25-75 (который разбивает исходные массивы на 25% -75%), а плохой - вне этого диапазона, а худший обычно находится в начале или в конце исходного массив. Но это?
Amumu
2
Здесь я говорю, что ось «плохая», если она делает большую часть больше, чем вы хотите, то есть размер. Что вы называете плохой , соответствует альфа = 3 / 4 . Я подозреваю, что суть вопроса в том, что ваш инструктор хотел, чтобы вы увидели, что порядок O ( ) ожидаемого времени работы не изменяется при изменении α . αnα=3/4O()α
Луи