Вероятность того, что два элемента сравниваются в рандомизированном QuickSort

Question

У меня есть проблема в определенной части рандомизированного анализа быстрого сортировки.

Согласно рандомизированному алгоритму быстросопортного сортировки Участие выбирается из заданного подмножества, на котором он вызывается из случайного индекса, а не только для выбора определенного индекса каждый раз.

Теперь предположим, что мы даем множество размеров, скажем, $ n $ на наш рандомизированный алгоритм Quicksort.

Теперь я прошу взглянуть на доказательство леммы-7.1 в тексте, приведенном ниже. Теперь мы дали массив нашему алгоритму, который может быть любой перестановки элементов, но в абзаце сразу после доказательства $ LEMMA-7.1 $ .

Почему автор рассматривает сортированный экземпляр нашего входного массива при выполнении анализа?

Более того, если посмотреть на текст после уравнения $ (7.2) $ где оправдало свою логику поиска вероятности того, что $ z_i $ сравниваются с $ z_j $ в нашем алгоритме. Теперь в том, что они рассматривают подмножество { $ z_i $ , ..., $ z_j $ }. Разве этот случай сравнения $ z_i $ , $ z_j $ Получение слишком специфических, если мы считаем, что только конкретное подмножество? Я хочу сказать, что мы используем рандомизированный подход, и вероятность сравнения может быть получена с использованием более широкого взгляда, такого как перестановка всех возможных случаев или около того.

Что мы используем определенное подмножество и которые слишком отсортированы, не убедительно, как мы получаем правильную вероятность для нашего алгоритма ...

     {z1,z2,...,zn} zi being the ith minimum element
            ^
            |
            ----------------------------------------------------
                                                                |                           
    --P(Zi is compared with Zj)                                 |
   |                                                            |
   |                                                            |
   |-----> We are considering                                   |
   |        Zij = {Zi,Zi+1,...,Zj} which is a subset of --------
   |
   |------ Aren't we considering a very specific case??

.

и вероятность $ 1 / (J-I + 1) $ -> Всего нет. элементов в подмножество также исправлено для Специфические $ i $ и $ j $

При рассмотрении вероятности сравнения $ z_i $ , $ z_j $ , подмножество, в котором Два элемента там, и которые должны быть разделены, может быть что-нибудь (то есть состоит из любого возможного элемента) и любого размера (не только $ J-I + 1 $ ) ...

может быть состояние рандомизации на самом деле делает все в аккаунт, но я не получаю это. Пожалуйста, вы можете объяснить мне логику, которую они используют, чтобы найти указанную вероятность, а также, пожалуйста, убедите меня, что мы правильно нахождаем вероятность сравнения.

Для справки Я прикрепляю соответствующие страницы введения в алгоритмы 3RD ED-- CLRS

Answer 1

Очень простое доказательство: я утверждаю, что если есть D целые числа со значениями между x и y, и существует n ≥ 2 элемента в массиве, то вероятность того, что x и y сравнивают 2 / (d + 2 ), независимо от n.

Доказательство по индукции: если n= 2, то, то четко d= 0, поэтому претензия заключается в том, что x и y сравниваются с вероятностью 2 / (0 + 2)= 1. Это также четко правильно, поскольку X и Y должны быть сравниваемым.

Теперь пусть n ≥ 3. Для первого разбиения мы выбираем поворот случайным образом. Каждый элемент массива сравнивается с поворотом, и другие сравнения не сделаны. Итак, если по совпадению мы выбираем x или y в качестве пивота, x и y будет сравнивать. Вероятность того, что составляет 2 / п. Если по совпадению мы выбираем один из D элементов с значениями между x и y, то разбиение будет перемещать x к одному разделу и y к другому, поэтому они никогда не сравниваются. Если мы выберем один из других элементов n - D - 2, то x и y в конечном итоге в том же разделе, а по индукции их сравниваются с вероятностью 2 / (d + 2).

Так что вероятность того, что сравнивается X и Y, составляет

2 / n + (n - d - 2) / n * 2 / (d + 2) = 

2 * (d + 2) / (n * (d + 2)) + 2 * (n - d - 2) / (n * (d + 2)) =

(d + 2 + n - d - 2) * 2 / (n * (d + 2)) =

2 * n / (n * (d + 2)) = 

2 / (d + 2) qed.

.

Это, конечно, тот же результат, что и Юваль, поскольку | J - I |= D + 1. Randomising делает анализ довольно простым - если мы сказали, например, «если n> 5, то мы выбираем 5 элементов случайным образом и выбираем медиану из этих 5 в качестве поворота», анализ будет гораздо более сложным.

PS. Доказательство в бумаге намного проще: при раздетении массива, $ x_i $ и $ x_j $ Оставайтесь в том же подразделении, пока не используется с i <= pivot <= j. Если этот пивот I или j, то $ x_i $ и $ x_j $ сравниваются, иначе они не по сравнению. Таким образом, шанс 2 / (ABS (J-I) + 1).

Answer 2

Идея доказательства - вычислить для любых двух элементов $ x, y $ в массиве, вероятность того, что они сравниваются в алгоритме. Эта вероятность может потенциально зависит от всего массива. Тем не менее, оказывается, что вы можете вычислить его только с учетом статистики порядка $ x, y $ , то есть их относительный порядок в отсортированном массиве. Если вы знаете, что $ x $ - это $ i $ маленький элемент в массиве и что $ y $ - это $ j $ маленький элемент в массиве, затем вероятность того, что $ x, y $ сравниваются - $ \ frac {2} {| ji | +1} $ .

Это не особый случай - каждый элемент $ x $ в массиве - это $ i $ Тю наименьший элемент, для некоторого значения $ i $ . Это просто соответствующая информация, которая позволяет рассчитать вероятность того, что $ x $ и $ y $ по сравнению.