С.А. Абрамов - Лекции о сложности алгоритмов (pdf) (1123764), страница 14
Текст из файла (страница 14)
В качестве алгоритма с указанными свойствами можно предложить следующий: при наличии вагонов на правой стороне узла к операции В прибегаем лишь тогда, когда на левой стороне невозможно увеличить на 1 число вагонов с правильным чередованием цветов с помощью какой-то из операций МИМОи ИЗ; в остальных случаях выполняется одна из операций МИМОи ИЗ, если возможны обе, то первая из них. Как и в задаче , считаем, что черных и белых вагонов по n штук, и n — размер входа.Какова сложность по числу сортировочных операций этого алгоритма в среднем?Указание.
Можно доказать следующие три утверждения.) Предположим, что в исходном расположении первый вагон на правойстороне белый. Тогда число сортировочных операций, требующихся алгоритму, равно 3n − k, где k есть количество максимальных сплошных последовательностей черных вагонов в исходном расположении (непосредственнослева и справа от каждой такой сплошной последовательности нет черныхвагонов, таков смысл «максимальности»).) Вновь предположим, что в исходном расположении первый вагон направой стороне белый.
Тогда количество исходных расположений, в которыхимеется ровноk максимальныхсплошных последовательностей черных ва nn−1гонов, есть.kk−1 nP− 1n−1n−12n − 2)=.k =1n−kknИз первых двух утверждений выводится, что искомая сложность в среднем естьnP−12n + 2 ·k =1(n − k) n n − 1 k 2n k−1,nтретье утверждение позволяет получить из этого, что интересующая нассложность естьn(5n − 3)51= n + + o(1).2n − 124. (Задача не связана со сложностью в среднем, но приводит к рекуррентному соотношению, которое решается сходно с (.).) Доказать, что для любого l > 0 можно, не применяя клей, построить изкостяшек домино, длина каждой из которых равна 2, навес длины lРешение принадлежит А.
П. Фокину.Глава . Сложность в среднем|{zl}Рис. . Навес из костяшек домино.(рис. ). Предложить алгоритм конструирования таких навесов, требующий O(el ) костяшек.Указание. Будем характеризовать навес из n костяшек неотрицательнымичислами l1 , l2 , ..., ln , где li — расстояние от правого края i-й сверху костяшкидо вертикальной (пунктирной на рис.
) линии, проходящей через правыйкрай -й, т. е. самой верхней, костяшки. (Таким образом, l1 = 0, ln = l .) Считая,что вес каждой костяшки равен 1, можно показать, что условием равновесияявляется система неравенствl i +1 ¶(l1 + 1) + (l2 + 1) + ... + (li + 1),ii = 1, 2, ..., n − 1(каждое такое неравенство означает, что центр тяжести конструкции изi верхних костяшек не выходит за правый край (i + 1)-й костяшки). Самыйдлинный навес получается тогда, когда числа l1 , l2 , ... подчинены рекуррентному соотношениюl i +1 =(l1 + 1) + (l2 + 1)... + (li + 1),il1 = 0.Далее можно идти тем же путем, что и при решении соотношения (.) и т.
д.. Перестановка (a1 , a2 , ..., an ) ∈ Πn называется полной, если ai 6= i,i = 1, 2, ..., n. Вероятность dn = Pn (Dn ) события Dn , состоящего в том,что данная перестановка является полной, равна 0 при n = 1 и равна(−1)n11− + ... +2!3!n!1при n > 1 (следствие: lim dn = ).en→∞(.)Задача о значении dn широко известна как задача о шляпах. Насобрание, состоявшееся поздно вечером, n его участников пришлив шляпах и оставили их в раздевалке, а когда собрание окончилось,разобрали шляпы наугад в темноте (в раздевалке перегорела лампочка) и разошлись по домам. Какова вероятность того, что каждыйпришел домой в чужой шляпе?Указание. Для любого r такого, что 0 ¶ r ¶ n, можно рассмотреть вероятность p(n, r) того, что перестановка длины n имеет ровно r непо-Задачидвижных точек (ровно r человек пришли домой в своих шляпах).
Тогда p(n, 0) + p(n, 1) + ... + p(n, n) = 1. Далее надо доказать, что p(n, r) =1n1p(n − r, 0) = p(n − r, 0), откуда будет следовать, что=rn(n − 1)...(n − r)r!11111d + d + d + ... +d + d = 0.0! n 1! n−1 2! n−1(n − 1)! n−1 n! 0С учетом d0 = 1 последнее соотношение однозначно определяет все d1 , d2 , ...Остается убедиться, что подстановка значений (.) в левую часть этого со-111(−1)r1−+−+ ...
+, r = 0, 1, ..., n,0!1!2!3!r!−jn nPiP(−1)в левую часть этого соотношения, получим(роль r играет n − j ).j =0 i=0 j! i!отношения дает 0. ПодставляяСлагаемые этой суммы можно перегруппировать так, чтобы внутри группызначение i + j было постоянной величиной l . Это дастn XlX(−1)il =0 i =0(l − i)! i!=n lX1 Xl =0l!i =0l!(−1)i ,(l − i)! i!последний шаг доказательства очевиден.. При быстрой сортировке (в любом из рассмотренных ее вариантов) число пар индексов (i, j), попадающих в стек отложенныхзаданий, не превосходит длины n исходного массива.. Верно ли, что определение усредненных затрат некоторогорандомизированного алгоритма требует задания распределения вероятностейа) на множестве всех допустимых входов?б) на каждом из множеств всех входов фиксированного размера?.
Если измерять затраты рандомизированной быстрой сортировки количеством обращений к генератору случайных чисел, то сложность этой сортировки есть величина порядка n. То же самое верно,если в определении функции затрат вместо математического ожидания взять максимум затрат по соответствующим сценариям.. Идея, лежащая в основе быстрой сортировки, может бытьиспользована для нахождения m-го наименьшего элемента средиa1 , a2 , ..., an , 1 ¶ m ¶ n (самый маленький элемент — это -й наименьший, следующий элемент — -й наименьший и т. д.). Разбиение массива с использованием случайно выбранного разбивающего элементапорождает два массива длины i − 1 и n − i при некотором 1 ¶ i ¶ n. Если m = i, то поиск закончен, если m ¶ i − 1, то далее рекурсивно находится m-й наименьший в первом массиве, а если m > i, то рекурсивнонаходится (m − i)-й наименьший во втором массиве.
Можно ввестисложность по числу сравнений при рассмотрении двух параметровГлава . Сложность в среднемn, m размера входа. Беря максимум этих сложностей по всем m та¯ким, что 1 ¶ m ¶ n, определяем сложности T(n), ¯T(n)по числу сравнений в худшем случае и в среднем с использованием n в качестве¯размера входа. Показать, что T (n) = Θ(n2 ) и ¯T(n)< 4n.Указание. Возьмем U(n) = max ¯T̄ (k).
Очевидно, что U(n) не убывает при1¶ k ¶ nвозрастании n и что ¯T̄(n) ¶ U(n). Доказывается неравенство1nU(n) ¶ (U(n − 1) + max{U(1), U(n − 2)} + ...... + max{U(n − 2), U(1)} + U(n − 1)) + n − 1,из которого, в силу неубывания U(n), следуетj k2nU(n) ¶U(n − 1) + U(n − 2) + ... + U+ n.n2Отсюда с помощью индукции выводится, что U(n) < 4n для всех n ¾ 1..
В инверсионном векторе (b1 , b2 , ..., bn ) произвольной перестановки (a1 , a2 , ..., an ) ∈ Πn каждая компонента bi равна количеству целых j таких, что 1 ¶ j < i и a j > ai . Например, инверсионный векторперестановки (2, 4, 3, 1, 6, 5) — это (0, 0, 1, 3, 0, 1). Показать, что каждому целочисленному вектору (b1 , b2 , ..., bn ), для которого 0 ¶ bi < i,i = 1, 2, ..., n, соответствует некоторая перестановка длины n, для которой этот вектор является инверсионным.Указание.
Очевидно, что если bn = k, 1 ¶ k < n, то an = n − k, и это соображение приводит к алгоритму построения (a1 , a2 , ..., an ), применимомук любому вектору b, удовлетворяющему оговоренным условиям: просматриваем компоненты вектора b, продвигаясь от последней к первой, находимзначение соответствующей компоненты перестановки a и удаляем найденное значение из множества M , первоначально равного {1, 2, ..., n}; при этомзначение ai , i = n, n − 1, ..., 1, определяется как (bi − 1)-й наибольший в множестве M (самый большой элемент — это первый наибольший, следующийпо величине элемент — это второй наибольший и т. д.).. Показать, что один этап пузырьковой сортировки понижает наединицу значение каждой неотрицательной компоненты инверсионного вектора перестановки (см. предыдущую задачу) и не изменяетнулевые компоненты.
Показать, что вероятность того, что значениемаксимума компонент инверсионного вектора выбранной наугад перестановки длины n равно k, 0 ¶ k < n, естьkn−k k!.n!Указание ко второй части задачи. Количество векторов (b1 , b2 , ..., bn ), длякаждого из которых bi ∈ N+ , 0 ¶ bi < i, i = 1, 2, ..., n, и max{b1 , b2 , ..., bn } ¶ k,Задачи1 ¶ k ¶ n − 1, равно k! kn−k−1 , так как bi может принимать любое значениемежду 0 и i − 1 при i ¶ k и любое значение между 0 и k − 1 для k < i ¶ n.. Показать, что математическое ожидание числа этапов пузырьковой сортировки совпадает с (.).Указание. Пользуясь решением предыдущей задачи, легко получить, чтоэто математическое ожидание естьn1 X(k(kn−k k! − (k − 1)n−k+1 (k − 1)!),n!что равноXn1n!k =1k =1(kn−k+1 k! − (k − 1)n−k+2 (k − 1)!) −nX(k − 1)n−k+1 (k − 1)! .k =1В упрощении последнего выражения поможет дискретный аналог формулыНьютона—Лейбница (см.
задачу ).. Используя идею решения задачи , предложить рандомизированный алгоритм восстановления перестановки длины n по ее инверсионному вектору (см. задачу ), имеющий сложность в среднемпо числу сравнений O(n2 ).. Пусть (a1 , a2 , ..., an ) — произвольная перестановка длины n. Еепреобразованиеfor i = n downto 2 do j := 1 + random(i − 1); ai ↔ a j od1. (Этоможет дать любую перестановку длины n с вероятностьюn!дает алгоритм построения случайных перестановок с равномернымраспределением вероятностей.). Предположим, что у нас нет другого генератора случайных чисел, кроме генератора, в результате обращения к которому появля1(аналог подбрасыванияется 0 или 1 с одинаковой вероятностью2монеты), и пусть p, 0 ¶ p ¶ 1, — заданное вещественное число. Каким образом с помощью этого генератора можно определить генератор randp, в результате обращения к которому появляется 0 или 1с вероятностями соответственно p и 1 − p (незначительные отклонения допустимы)? Сложность в среднем алгоритма получения одногослучайного числа с помощью randp должна быть меньше 2 (затратыопределяются числом обращений к изначально имеющемуся генератору).Указание.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
