Позвольте 0 < a < 0.5 быть константой. У нас есть массив n-element. Рандомизированная quicksort выбирает один элемент из массива равномерно случайным образом как свод и разделы. С какой вероятностью наименьшая секция будет больше an. мой короткий ответ в примечании говорит с вероятностью 1-2a. любой мог сказать, как рассчитывается эта вероятность?Самая маленькая часть в разделе Быстрая сортировка с некоторыми условиями?
Размер меньшего раздела равномерно распределен в диапазоне [0, n/2], поэтому вероятность того, что он будет меньше an, составляет an/(n/2). Поэтому вероятность того, что она будет больше a, равна 1 - an/(n/2). an/(n/2) - это точно 2a, следовательно вероятность 1 - 2a.
Вот диаграмма, в случае, если это помогает:
Pivot positions
a·n n/2 a·n+n/2 n
v v v v
<---------------------|||||||·---------------------|||||||>
/---^---\ /---^---\
smaller partition on left smaller partition on right
bigger than a·n bigger than a·n
size: n/2 - a·n size: n - (a·n + n/2)
Total size: n - 2a·n
Probability: 1 - 2a
Неужели я не мог получить его. возможно ли это объяснить? –
@mio: если я выбираю случайное число от 0 до 100, какова вероятность того, что он меньше 20? Что он больше 20? Что, если диапазон был от 0 до 50? Это ничем не отличается. – rici
Я думаю, что случайный стержень имеет такое же распределение, что и x_i для i, выбираемого равномерно случайным образом из {1, ..., n}. Размер меньшего раздела - min (i-1, n-i). Если I - множество индексов i таких, что min (i-1, n-i) ≥an, то вероятность равна | I |/n. но не может продолжаться отсюда ... –