Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 32
Текст из файла (страница 32)
В представленном выше псевдокоде наиболее трудоемкая процедура — сортировка в строке 5. Как будет показано в главе 8, если использовать сортировку сравнением, то время ее работы составит П(п 18 н). Эта нижняя грань достижима„ поскольку мы уже убедились, что сортировка слиянием выполняется в течение времени 9(п !пи). (В части!1 книги мы познакомимся и с другими видами сортировки, время работы которых также равно 9(н 18 и).
В упр. 8.3.4 предлагается решить очень похожую задачу сортировки чисел в диапазоне от О до пз — 1 за время 0(п).) Если после сортировки приоритет Р[!] является дьм в порядке возрастания, то элемент А[!] на выходе алгоритма будет расположен в позиции с номером 51 Таким образом, мы достигнем требуемой перестановки входных данных, Осталось доказать, что в результате выполнения этой процедуры будет получена случайная перестановка с равномерным распределением, другими словами, что все перестановки чисел от 1 до и генерируются с одинаковой вероятностью.
Лемма 5.4 В предположении отсутствия одинаковых приоритетов в результате выполнения процедуры Рекм15те-еу-ЯоктичО получается случайная перестановка входных значений с равномерным распределением. Доказагнельсгнво. Начнем с рассмотрения частной перестановки, в которой каждый элемент А[!] получает 1-й приоритет в порядке возрастания. Покажем, что вероятность такой перестановки равна 1/и!.
Обозначим через Е; (! = 1, 2,..., и) событие, состоящее в том, что элемент А[1] получает 1-й приоритет. Теперь вычислим вероятность того, что события Е; происходят для всех !. Эта вероятность равна Рг (Е1 Г1 Ез Г1 Ез П . О Е„л П Е„) Часть ! Основм 152 Воспользовавшись результатами упр. В.2.5, можно показать, что эта вероятность равна Рг (Ез) Рг (Ез ] Ег) .
Рг (Ез ] Ез П Е~) Рг (Е4 [ Ез Г1 Ез Г1 Е~) Рг (Е, ] Е, ~ Г1 Е, .з Г1 О Ез) . Рг (Е„] Е„~ О . Г1 Е~) Мы имеем Рг (Ег) = 1/и, поскольку это вероятность того, что приоритет выбранного наугад одного из п элементов окажется минимальным. Теперь заметим, что Рг (Ез ] Е~) = 1/(и — 1), поскольку при условии, что приоритет элемента А[Ц минимальный, каждый из оставшихся п — 1 элементов имеет одинаковые шансы располагать вторым наименьшим приоритетом. В общем случае для 1 = 2, 3,..., п выполняется соотношение Рг (Е; ] Е, ~ О Е, з О .. О Е~ ) = 1/(и — 1+1), поскольку при условии, что приоритеты элементов от А[Ц до А[1 — Ц равны от 1 до 1 — 1 (в порядке возрастания), каждый из оставшихся и — (1 — 1) элементов имеет одинаковые шансы располагать 1-м наименьшим приоритетом.
Таким образом, справедливо следующее выражение: Рг(Е~ПЕзГ1ЕзГ1 йń— дйЕ ) = ( — ) ( ) ( — ) ( — ) 1 и! и мы показали, что вероятность получения тождественной перестановки равна 1/и!. Зто доказательство можно обобщить на случай произвольной перестановки приоритетов. Рассмотрим произвольную фиксированную перестановку и = (п(1), о(2),..., п(п)) множества (1,2,...,и). Обозначим как г, ранг приоритета, присвоенного элементу А[1], причем элемент с 5-м приоритетом имеет ранг, равный 51 Если мы определим Е, как собьпие, при котором элемент А[1] получает п(г)-й приоритет (те. г, = а.(1)), то можно будет провести доказательство, аналогичное приведенному выше. Таким образом, при вычислении вероятности получения той или иной конкретной перестановки рассуждения и расчеты будут идентичными изложенным выше. Поэтому вероятность получения такой перестановки также равна 1(п.'.
Возможно, некоторые читатели сделают вывод, что для доказательства того, что все случайные перестановки распределены с равной вероятностью, достаточно показать, что для каждого элемента А[1] вероятность оказаться в позиции 5 равна 1/и. Выполнив упр. 5,3А, можно убедиться, что это условие недостаточное. Более предпочтительный метод получения случайной перестановки — перестановка элементов заданного массива "на месте". С помощью процедуры КАМООм17е-1х-РеАсе эту операцию можно выполнить за время 0(п). В ходе 1-й итерации элемент А[1] случайным образом выбирается из множества элементов от А[1] до элемента А[п], после чего в последующих итерациях этот элемент больше не изменяется.
!55 Глава 5. Яерантностный анализ и рандамизированные алгоритмы Нзз!м'ООм!ее-1х-Реясе (А) ! и = А.1епдгл 2 Гог з = 1 Го п 3 Обменять А[з] и А[Клмпом(з, и)] Покажем с помощью инварианта цикла, что в результате выполнения процедуры КАхООм!Ее-1н-Релсе получаются случайные перестановки с равномерным распределением. Назовем !е-перестановкой (размещением) данного п-элементного множества последовательность, состоящую из к элементов, выбранных среди п элементов исходного множества (см.
приложение В). Всего имеется п)/(и — к) ! возможных к-перестановок. гуемма 5.5 Процедура Клипом!ее-1н-Релсе вычисляет равномерно распределенные пере- становки. Доказалзеяьслзво. Используем следующий инвариант цикла. Непосредственно перед з-й итерацией цикла 1ог в строках 2 и 3 для каждой возможной (з — 1)-перестановки п элементов вероятность того, что подмассив А[1 .. з — Ц содержит эту (з — 1)-перестановку, равна (и — з + 1))/и!.
Необходимо показать, что это утверждение истинно перед первой итерацией цикла, что итерации сохраняют истинность инварианта и что оно позволяет показать корректность алгоритма по завершении цикла. Инициализации. Рассмотрим ситуацию непосредственно перед первой итерацией цикла, так что з = 1. Согласно формулировке инварианта цикла вероятность нахождения каждого размещения из 0 элементов в подмассиве А[1 .. 0] равна (п — з' + 1)!/п! = и)/п! = 1.
Подмассив А[1 .. 0] — пустой, а 0-размещение по определению не содержит ни одного элемента. Таким образом, подмассив А[1 .. О] содержит любое 0-размещение с вероятностью 1, и инвариант цикла перед первой итерацией выполняется. Сохранение. Мы считаем, что перед з-й итерацией вероятность того, что в подмассиве А[1.,1 — Ц содержится заданное размещение з — 1 элементов, равна (и — з + 1)(/и!. Теперь нужно показать, что после з-й итерации каждая из возможных з-перестановок может находиться в подмассиве А[1..з] с вероятностью (и — з)!/п!. Тогда увеличение з на следующей итерации приведет к сохранению инварианта цикла. Изучим з'-ю итерацию.
Рассмотрим некоторое конкретное размещение з элементов и обозначим его элементы как (хы хз, ..., х,). Это размещение состоит из размещения з — 1 элементов (хы..., яч з)„за которым следует значение х„которое помещается в ходе выполнения алгоритма в элемент А[з]. Пусть Е1 обозначает событие, при котором в результате первых з — 1 итераций в подмассиве А[1 .. з — Ц создается определенное размещение з — 1 элементов (хз,..., к, з).
Согласно инварианту цикла Рг(Е1) = (и — з'+ 1)(/и!. Часть 1 Основы 154 Пусть теперь Ез — событие, при котором в ходе 1-й итерации в позицию А[г) помещается элемент х,. Размещение (хы, .., х,) формируется в подмассиве А[1., 1[ только при условии, что происходят оба события — и Еы и Ез, — так что мы должны вычислить значение Рг (Ез й Е~ ). Воспользовавшись уравнением (В.14), получаем Рг (Ез Г~ Ег ) = Рг (Ег [ Е~ ) Рг (Е)) Вероятность Рг (Ез [ Е~ ) равна 1/(и — г' + 1), поскольку в строке 3 алгоритм выбирает х, случайным образом среди и — 1+ 1 значений в позициях А[1 .. и].
Таким образом, мы имеем Рг (Ез П Ег) = Рг (Ез [ Е~) Рг (Ег) 1 (и — 1+ 1)! и — 1+1 и! (и — 1)! и'. Завершение. При завершении алгоритма 1 = и + 1, и подмассив А[1 .. и) представляет собой заданную и-перестановку с вероятностью (и — (и+1)+1)!/и! = О!/и! = 1/и!. Таким образом, процедура КхмпОм12е-1ы-РьАсе генерирует равномерно распределенные случайные перестановки. Рандомизированный алгоритм зачастую является самым простым и наиболее эффективным средством решения задачи. Время от времени вы будете встречаться с такими алгоритмами в данной книге. Упражнения 5.3.1 У профессора возникли возражения против инварианта цикла, использующегося при доказательстве леммы 5.5.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
