Блог

Главная - Вопросы по программированию - рандомизированная быстрая сортировка: вероятность низкого размера раздела 1

рандомизированная быстрая сортировка: вероятность низкого размера раздела 1

#algorithm

#алгоритм

Вопрос:

В рандомизированной быстрой сортировке вероятность получения низкого раздела размером 1 оказывается равной 2 / n. Я пытался разобраться в этом, но не мог понять, как.

Выражение, которое я получаю, является: 

 X = low partition size
P(X=1) = 1/n   1/n
[Summation(i = 2 to n) 
{
  (n-i Comb i-1)/(n-1 Comb i-1)
}
]

это сводится к:

 = 1/n   1/n[(n-2)/(n-1)   (n-3)(n-4)/(n-1)(n-2)   ...]

Как двигаться дальше?
Верны ли мой подход и выражение?

Ответ №1:

вероятность получения низкого раздела размером 1 оказывается равной 2 / n

Это зависит от того, что вы подразумеваете под «низким разделом размера 1». Если вы посмотрите на худший случай для быстрой сортировки:

Наиболее несбалансированный раздел возникает .. если стержень оказывается наименьшим или наибольшим элементом в списке

При равномерном выборе вероятность выбора самого низкого элемента равна 1 / n, как и вероятность выбора самого высокого элемента. Поскольку это непересекающиеся события (когда элементы не все одинаковые), то общая вероятность равна их сумме: 2 / n.

Вероятность того, что левая часть раздела равна 1, равна половине этого: 1 / n .

Комментарии:

1. Я тоже так думал. таким образом, вероятность получения 1, n-1 (или n-1, 1) будет равна 2 / n, имеет смысл, но так же было бы получение q, n-q (или n-q, q). Я изучал это у TH Cormen, и в нем явно указано, что вероятность получения 1, n-1 в два раза выше, чем при получении любой другой конфигурации. Ссылка на раздел 8.2 (значение q = 1 в два раза выше, чем любое другое значение q)

2. @Skartik я проверю это. Это может быть связано с тем, как pivot определяется в разделе этой конкретной версии. В будущем, если ваш вопрос зависит от конкретной версии алгоритма, я предлагаю вам явно указать это в вопросе.

3. Да, пожалуйста. Спасибо

4. @skartik Итак, я проверил это раньше в CLRS, и в обеих версиях, которые я видел, быстрая сортировка находится в главе 7, и я не могу найти там ваше утверждение. Не могли бы вы опубликовать свой вопрос 1. Псевдокод, используемый в вашей версии и 2. цитата из заявления? Спасибо.

5. Его глава 8 для меня в Cormen: Анализ быстрой сортировки -> Анализ среднего случая -> Анализ разбиения -> повторение для среднего случая