Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 30
Текст из файла (страница 30)
В лемме 5.2 делается предположение о виде входных данных. В лемме 5.3 такие предположения отсутствуют, хотя для рандомизацин входных величин требуется дополнительное время. В оставшейся части настоящего раздела обсуждаются некоторые вопросы, связанные с входными данными, которые подверглись случайной перестановке. Массивы, полученные в результате случайной перестановки Во многих алгоритмах входные данные рандомизируются путем перестановки элементов исходного входного массива (впрочем, существуют и другие способы рандомизации). Мы рассмотрим два метода, позволяющие выполнить эту операцию.
Будем считать, что у нас имеется массив А, который содержит элементы от 1 до п. Наша цель — случайным образом переставить элементы массива. Один из распространенных методов заключается в том, чтобы присвоить каждому элементу А [г) случайный приоритет Р 11), а затем отсортировать элементы массива А в соответствии с их приоритетами. Например, если исходный массив имеет вид А = (1, 2, 3, 4) и выбраны случайные приоритеты Р = (Зб, 3, 97, 19), то в результате будет получен массив В = (2,4, 1, 3), поскольку приоритет второго элемента самый низкий, за ним по приоритету идет четвертый элемент, после него — первый и, наконец, третий.
Назовем эту процедуру Рекмоте Ву Боктпчо: Рекмоте ВУ БОкт!х0(А) 1 п — 1епуЯА) 2 1ог г' - 1 Го п 3 йо Р11] = Влнпом(1, пз) 4 Отсортировать массив А с ключом сортировки Р 5 ге1нгп А В строке 3 выбирается случайное число от 1 до пз. Такой интервал выбран для того, чтобы снизить вероятность наличия одинаковых приоритетов в массиве Р. (В упражнении 5.3-5 требуется доказать, что вероятность отсутствия в массиве одинаковых приоритетов составляет по меньшей мере 1 — 1/и, а в упражнении 5.3-6 — реализовать алгоритм, даже если несколько приоритетов могут иметь одинаковые значения.) Будем считать, что одинаковых приоритетов в массиве нет.
Часть!. Основы 152 В представленном выше псевдокоде наиболее трудоемкая процедура — сортировка в строке 4. Как будет показано в главе 8, если использовать сортировку сравнением, то время ее работы будет выражаться как й (и 18 и). Эта нижняя грань достижима, поскольку мы уже убедились, что сортировка слиянием выполняется в течение времени 9 (и 18 и). (Во второй части книги мы познакомимся и с другими видами сортировки, время работы которых также имеет вид 6 (и 18 и).) Если приоритет Р [г] является 1'-м в порядке возрастания, то после сортировки элемент А [г] будет расположен в позиции с номером 1 Таким образом мы достигнем требуемой перестановки входных данных. Осталось доказать, что в результате выполнения этой процедуры будет получена случайная перестановка с равномерным распределением, другими словами, что все перестановки чисел от 1 до и генерируются с одинаковой вероятностью.
Лемма 5.4. В предположении отсутствия одинаковых приоритетов в результате выполнения процедуры Редмцте Ву 30ктпчс получается случайная перестановка входных значений с равномерным распределением. Доказательство. Начнем с рассмотрения частной перестановки, в которой каждый элемент А [г] получает з'-й приоритет (в порядке возрастания). Покажем, что вероятность такой перестановки равна 1/и!. Обозначим через Х; (г = 1, 2,..., и) событие, состоящее в том, что элемент А [г] получает 1-й приоритет. Теперь вычислим вероятность того, что события Х; происходят для всех г. Эта вероятность равна Рг (Х~ П Хз П Хз П...
П Х„~ П Х„) . Воспользовавшись результатами упражнения В.2-6, можно показать, что эта ве- роятность равна Рг(Хз) Рг(Хз [Х~) Рг(Хз [Хз ПХ~) Рг(Х4 [Хз ПХг ПХ~) Рг (Х; [ Х, д П Х, з П... П Х~) ... Рг (Х [ Х г П... П Хг) . Вероятность события Х~ равна Рг (Х~ ) = 1/и, поскольку это вероятность того, что приоритет выбранного наугад одного из и элементов окажется минимальным.
Теперь заметим, что Рг (Хз [ Хг) = 1/(и — 1), поскольку при условии, что приоритет элемента А [1] минимальный, каждый из оставшихся и — 1 элементов имеет одинаковые шансы располагать вторым наименьшим приоритетом. В общем случае при г = 2,3,...,п выполняется соотношение Рг(Х, [ Х; ~ П Х, з П... П ПХг) = 1/(и — г + 1), поскольку при условии, что приоритеты элементов от А [1] до А [г — 1] равны от 1 до г — 1 (в порядке возрастания), каждый из оставшихся п — (4 — 1) элементов имеет одинаковые шансы располагать г-м наименьшим приоритетом. Таким образом, справедливо следующее выражение: Рг (Хг П Хз П Хз П...
П Х„~ П Х„) = Глава 5. Вероятностный анализ н рандомнзнрованные алгоритмы 153 Тем самым доказано, что вероятность получения тождественной перестановки равна 1/и!. Это доказательство можно обобщить на случай произвольной перестановки приоритетов. Рассмотрим произвольную фиксированную перестановку т = = (п(1),п(2),...,п(п)) множества (1,2,...,и). Обозначим через г; ранг приоритета, присвоенного элементу А [1], причем элемент с 1-м приоритетом имеет ранг, равный 3. Если мы определим Х; как событие, при котором элемент А [1] получает о (г)-й приоритет (т.е. г, = о (г)), то можно провести доказательство, аналогичное приведенному выше. Таким образом, при вычислении вероятности получения той или иной конкретной перестановки рассуждения и расчеты будут идентичными изложенным выше.
Поэтому вероятность получения такой перестановки также равна 1/и!. И Возможно, некоторые читатели сделают вывод, что для доказательства того, что все случайные перестановки распределены с равной вероятностью, достаточно показать, что для каждого элемента А [г] вероятность оказаться в позиции 3 равна 1/и.
Выполнив упражнение 5.3-4, можно убедиться, что это условие недостаточное. Более предпочтительным методом получения случайной перестановки является способ, который заключается в перестановке элементов заданного массива "на месте". С помощью процедуры КАн1юмые 1н Р~.Асе эту операцию можно выполнить за время 0(п). В ходе 1-й итерации элемент А [г] случайным образом выбирается из множества элементов от А [г] до элемента А [и], после чего в последующих итерациях этот элемент больше не изменяется: ЙАнгюм!ее 1н РьАсе(А) 1 и — 1епдй[А] 2 1ог г' — 1 то и 3 г)о Обменять А[1] ~ А[КА пюм(г, и)] Покажем с помощью инварианта цикла, что в результате выполнения процедуры КАн1юм1ге 1м Р~.Асе получаются случайные перестановки с равномерным распределением.
Назовем lс-перестановкой (размещением) данного и-элементного множества последовательность, состоящую из )г элементов, выбранных среди и элементов исходного множества (см. приложение В). Всего имеется и!/(и — 1с)! возможных Й-перестановок. Лемма 5.5. В результате выполнения процедуры ВАмюмыЕ 1н Р~.АОЕ получа- ются равномерно распределенные перестановки. 154 Часть !. Основы Доказательсиюво. Воспользуемся сформулированным ниже инварнантом цикла. Непосредственно перед г-й итерацией цикла 1ог нз строк 2-3, вероятность того, что в подмасснве А [1..г — 1] находится определенная (г — 1)-перестановка, равна (и — г + 1) !/и!. Необходимо показать, что это утверждение истинно перед первой итерацией цикла, что итерации сохраняют истинность инварианта и что оно позволяет показать корректность алгоритма по завершении цикла. Инициализация.
Рассмотрим ситуацию, которая имеет место непосредственно перед первой итерацией цикла (г = 1). Согласно формулировке инварианта цикла, вероятность нахождения каждого размещения из 0 элементов в подмассиве А [1..0] равна (п — 1+ 1))/и! = пЦп! = 1. Подмассив А [1..0]— пустой, а 0-размещение по определению не содержит ни одного элемента.
Таким образом, подмасснв А [1..0] содержит любое 0-размещение с вероятностью 1, и инвариант цикла выполняется перед первой итерацией. Сохранение. Мы считаем, что перед г-ой итерацией вероятность того, что в подмассиве А [1..г — 1] содержится заданное размещение г — 1 элементов, равна (и — 1+ 1)!/и!. Теперь нам нужно показать, что после г-ой итерации каждая из возможных г-перестановок может находиться в подмассиве А [1.л] с вероятностью (и — г) !/п!. Рассмотрим г'-ю итерацию. Рассмотрим некоторое конкретное размещение г элементов и обозначим его элементы как (хы хз,..., х;). Это размещение состоит из размещения г — 1 элемента (хм ха,..., х; 1), за которым следует значение х,, которое помещается в ходе выполнения алгоритма в элемент А [г].
Пусть Е1 обозначает событие, при котором в результате первых г — 1 итераций в подмассиве А [1..г — 1] создается определенное размещение ь' — 1 элементов (хм ха,..., х; 1). Согласно инварианту цикла, Рг(Е1) = = (п — г'+ 1) (/и!. Пусть теперь Ез — событие, при котором в ходе г-ой итерации элементу А [1] присваивается значение х;. Размещение (хм хз,..., х ) формируется в подмассиве А [1.л] только при условии, что происходят оба события — и Ем и Ез, так что мы должны вычислить значение Рг (Ез П Ег). Воспользовавшись уравнением (В.14), получаем: Рг (Ег г! Е1 ) = Рг (Ег [ Е1 ) Рг (Ез ) . Вероятность Рг (Ез [ Е1) равна 1/(и — г'+ 1), поскольку в строке 3 алгоритма производится случайный выбор величины х; из п — г + 1 элемента подмассива А [г..п].
Таким образом, получаем: Рг(Ез П Е1) = Рг(Ез [ Е1 ) Рг(Е1) = 1 (и — 1+ 1)! (и — 1)! и — г'+ 1 и! и! Глава 5. Вероятностный анализ и рандомизированные алгоритмы 155 Завершение. После завершения алгоритма т = и+ 1, поэтому заданное размещение и элементов находится в подмассиве А [1..п] с вероятностью (п — и) Цп! = 1/и!. Таким образом, в результате выполнения процедуры Клноом12е 1н Р1.лсе получаются равномерно распределенные случайные перестановки. Рандомизированный алгоритм зачастую является самым простым и наиболее эффективным путем решения задачи.
Время от времени вы будете встречаться с такими алгоритмами в данной книге. Упражнения 5.3-1. У профессора возникли возражения против инварианта цикла, использующегося при доказательстве леммы 5.5. Он сомневается, что этот инвариант выполняется перед первой итерацией. Согласно его доводам, пустой подмассив не содержит никаких размещений из О элементов, поэтому вероятность того, что в таком подмассиве находится то или иное размещение, должна быть равна О. Из этих рассуждений следует, что инвариант цикла перед первой итерацией не выполняется.
Перепишите процедуру Илноом1ге 1н Роллсе таким образом, чтобы связанный с нею инвариант цикла перед первой итерацией применялся к непустому подмассиву, и соответствующим образом моднфицируйте доказательство леммы 5.5. 5.3-2. Профессор решил разработать алгоритм, в результате выполнения которого получались бы все случайные перестановки, кроме тождественной. Он предложил такую процедуру: Рекм11те %1тно11т 1Рент!т'1'(А) 1 и — !епд1й[А] 2 1ог 1 - 1 1о и — 1 3 йо Обменять А[1] + А[йлнпом(1+1,п)] Добьется ли профессор поставленной цели с помощью этого кода? 5.3-3.
Предположим, что вместо того, чтобы менять местами элемент А [т] со случайно выбранным элементом из подмассива А [1..п], мы меняем его местами с любым случайно выбранным элементом массива А: РЕКМ11ТЕ %1ТН А1.1.(А) 1 и ~ — !епдЖ[А] 2 1ог 1 — 1 1о и 3 йо Обменять А[в] А[КЛНООМ(1, и)] Получится ли в результате выполнения этого кода равномерная случайная перестановка? Обоснуйте ваш ответ. 156 Часть 1. Основы 5.3-4. Профессор предложил для генерирования случайных перестановок с однородным распределением такую процедуру: Рнймитн Ву Сусле(А) 1 п ~ — 1еидй[А] 2 о„[гвен ~ — КАьлэОМ(1, п) 3 1огг — 1 гоп 4 бо аевв — г+ обве$ 5 1в Невв ) и б Феп Певв — г1евв — п 7 В[Ыев1] — А[в] 8 гетпгп В Покажите, что элемент А [1] оказывается в определенной позиции массива В с вероятностью 1/и.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
