рандомизированная быстрая сортировка: вероятность сравнения двух элементов?

Question

Я читаю " Вероятность и вычисления " М. Митценмахера и Э. Упфаля. У меня проблемы с пониманием того, как вычисляется вероятность сравнения двух элементов.

Ввод: отсортированный список (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: список отсортирован изначально.

Answer 1

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

На каждом шаге пивот выбирается из последовательности (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. Вероятность сравнения двух элементов на неизвестном рекурсивном шаге - это то, что я объяснил выше.

Answer 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).