Лекции о сложности алгоритмов. С. А. Абрамов (1121249), страница 14
Текст из файла (страница 14)
.].ЗадачиЕще один путь получения этого же результата. Так как вероятность p удачного выбора индекса i больше половины, то математическое ожидание количества попыток, которые потребуются для получения удачного значения i, меньше двух. Отсюда среднее число сравнений a меньше, чем 2(n − 1).Теоретически нет никакого препятствия к тому, чтобы при определении функции затрат рандомизированного алгоритма взять вместо математического ожидания максимум затрат по соответствующим сценариям (при таком подходе рандомизированная быстрая сортировка имеет квадратичную сложность).
Но обычно длярандомизированных алгоритмов рассматриваются усредненные затраты.Добавим в заключение, что правомерен взгляд на рандомизированные алгоритмы, при котором каждому возможному входу сопоставляется вероятностное пространство обычных детерминированных алгоритмов . Если в этой связи вернуться к примеру ., томожно заметить, что для разрезания полоски бумаги каждый из рассматриваемых сценариев задает конкретный детерминированный алгоритм разрезания.Мы вернемся к этому в § .Задачи. Верно ли, что для рассмотрения сложности в среднем некоторого алгоритма требуется задание распределения вероятностейа) на множестве всех допустимых входов?б) на каждом из множеств всех входов фиксированного размера?. Как говорилось при обсуждении асимптотического закона распределения простых чисел, в [] приводится элементарное доказательство неравенств Чебышева с C = 6, c = 1/3.
Добавим, что наиболее легко доказывается нижняя оценкаπ(n) >1 n,3 ln nсправедливая для всех n > 1. Доказать, что сложность в среднем алгоритма пробных делений не является полиномиально ограниченной,используя для этого только последнее неравенство и не прибегаяк полному варианту асимптотического закона распределения простыхчисел.См., например, [].Глава .
Сложность в среднемУказание. Предположение о том, что V (m) < 23m/4 для всех m > m0 , позволило бы, исходя из равенстваπ(2m ) = π(2m0 ) + V (m0 + 1) + V (m0 + 2) + ... + V (m),вывести верхнюю оценку π(2m ) = O(23m/4 ), что вступило бы в противоре2mчие с неравенством π(2m ) ¾ cс положительной константой c. Поэтомуmсуществует последовательность m1 < m2 < ... натуральных чисел таких, чтоV (mi ) ¾ 23mi /4 , i = 1, 2, ... Можно рассмотреть (.) для m = m1 , m2 , .... Сложность по числу перемещений (обменов) в среднем длясортировки выбором при условии, что мы исключаем обмены вида1xk ↔ xk , не превосходит n − 2 + , где n — длина массива.nУказание.
В перестановках из Πn среднее число элементов ai , 1 ¶ i ¶ n − 1,таких, что ai = i, естьn−1(см. пример .).n. Найти среднее число присваиваний m := ... при выполненииалгоритма поиска наименьшего элемента массива:m := x 1 ;for i = 2 to n doif xi < m then m := xi fiodПредполагается, что все возможные взаимные порядки элементовв исходном массиве длины n являются равновероятными; в качестверазмера входа берется n.Указание. Рассмотреть разложение всего вероятностного пространства всумму двух событий: последний элемент исходного массива является его наи1меньшим элементом (вероятность равна ) и соответственно последний элеnмент исходного массива не является его наименьшим элементом (вероятn−1ность равна).
Пусть s(n) обозначает искомое математическое ожидание.nПоказать, что условное математическое ожидание исследуемого числа присваиваний, соответствующее первому событию, есть s(n − 1) + 1, а условноематематическое ожидание, соответствующее второму событию, есть s(n − 1).Пользуясь формулой полного математического ожидания, вывести отсюда рекуррентное соотношение для s(n) и найти его решение, удовлетворяющееусловию s(1) = 1.. Пользуясь дискретным аналогом формулы Ньютона—ЛейбниnPца, согласно которому( f (k + 1) − f (k)) = f (n + 1) − f (1), вычислить суммуnPk =1k =11, входящую в (.).k(k + 1)Задачи.
Исходя из (.), пользуясь приемом оценки сумм из приложения B и результатом из предыдущей задачи, доказать неравенство ¯T¯QS (n) ¶ 2n ln n, из которого будет следовать, что величина O(n)в правой части (.) отрицательна.. Вернемся к задаче . В качестве алгоритма с указанными свойствами можно предложить следующий: при наличии вагонов на правой стороне узла к операции В прибегаем лишь тогда, когда на левой стороне невозможно увеличить на 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!последний шаг доказательства очевиден..
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
