рандомизированный quicksort: вероятность двух сравнений элементов?
Я читаю "Вероятность и Вычисляю" M.Mitzenmacher и E.Upfal. У меня есть проблемы при понимании, как вероятность сравнения двух элементов вычисляется.
Вход: отсортированный список (y1, y2..., yN) чисел. Мы ищем элемент центра (случайным образом). Вопрос: что такое вероятность, что два элемента yi и yj (j> i) будет сравнен?
Ответ (из книги): yi и yj будут сравнены, если или yi или yj будут выбраны как центр в первой ничьей от последовательности (yi, yi+1..., yj-1, yj). Таким образом, вероятность: 2 / (j-i+1).
Проблемой для меня является начальное требование: например, взятие yi в первой ничьей из целого списка вызовет сравнение с yj (и наоборот), и вероятность является 2/n.
Так, скорее "обратное" требование верно - ни один из (yi+1..., yj-1), элементы могут быть выбраны, прежде yi или yj, но размер "пула" не фиксируется (в первой ничьей, это - N наверняка, но на втором это меньше).
Кто-то мог объяснить, как авторы придумывают такое упрощенное заключение?
Edit1: некоторая хорошая душа полировала мое сообщение, спасибо :-).
Edit2: список отсортирован первоначально.
2 ответа
Ответ авторов правильный, хотя я до сих пор не понимаю, как они пришли к такому выводу так легко и быстро.
Обозначим через L = j-i + 1. Фактические значения j и i здесь не имеют значения, важно L. Обозначим также через P (N, L) вероятность сравнения элементов yi и yj из упорядоченной последовательности чисел размера N.
Факты:
- ] P (N, 2) = 1
- P (N, L) = 2 / N + 1 / N * (P (N-1, L) + P (N-2, L) + P (N- 3, L) + ... + P (L, L))
Эта сумма выглядит некрасиво, но после двух тестов выяснилось, что P (N, L), вероятно, равно 2 / L. Давайте проверим это:
- P (N, L = 2) = 1 = 2/2 = 2 / L
- предположим, что P (N, L) = 2 / L
- P (N + 1, L) = 2 / (N + 1) + 1 / (N + 1) * (P (N, L) + ... P (L, L)) = 2 / (N + 1) + (N-L +1) * 1 / (N + 1) * 2 / L = 2 / L
И так как L = j-i + 1, мы получаем 2 / (j-i + 1).
Quicksort работает, сравнивая каждый элемент с точкой поворота: те, которые больше, чем точка поворота, помещаются справа от оси, а те, что не больше, слева (или наоборот, если вы хотите сортировку по убыванию, это не так '' t имеет значение).
На каждом шаге точка поворота выбирается из последовательности (yi, yi + 1, ..., yj) . Сколько элементов в этой последовательности? j - i + 1 (я думаю, у вас была опечатка, это не может быть y - i + 1 ).
Таким образом, вероятность выбора одного из двух конкретных элементов из этого списка, очевидно, равна 2 / (j - i + 1) .
Проблема для меня - это первоначальное утверждение: например, выбор yi в первом розыгрыше из всего списка приведет к сравнению с yj (и наоборот), и вероятность будет равна 2 / n.
Если выбрать yi , он будет сравниваться только с другими элементами j - i . Откуда у вас n ? Помните, что ваш список идет только от yi до yj !
Правка :
Читая вопрос еще раз, я нахожу его немного двусмысленным. Вероятность сравнения двух элементов на первом этапе рекурсии действительно равна 2 / n , как вы говорите, потому что i и j равны 1 и n . Вероятность сравнения двух элементов на неизвестном рекурсивном шаге - это то, что я объяснил выше.