Глава 2. Сложность в среднем

s_^_J

Рис. 11. Навес из костяшек домино.

(рис. 11). Предложить алгоритм конструирования таких навесов, тре­бующий O(el) костяшек.

Указание. Будем характеризовать навес из n костяшек неотрицательными числами l_1;l₂, ...,l_n, где l_i — расстояние от правого края i-й сверху костяшки до вертикальной (пунктирной на рис. 11) линии, проходящей через правый край 1-й, т. е. самой верхней, костяшки. (Таким образом, l_t = 0, l_n = l.) Считая, что вес каждой костяшки равен 1, можно показать, что условием равновесия является система неравенств

l_i+1<^ai+ⁱ)+^fe+ _i )+-+^ai+ⁱ) , i=i,2,...,n-i

(каждое такое неравенство означает, что центр тяжести конструкции из i верхних костяшек не выходит за правый край (i + 1)-й костяшки). Самый длинный навес получается тогда, когда числа l_1;l₂, ... подчинены рекуррент­ному соотношению

l_i+i = i > li=°-

Далее можно идти тем же путем, что и при решении соотношения (7.2) и т. д.

31. Перестановка (a_ъ a₂,..., a_n) е П_n называется полной, если a_i ф i, i = l,2,...,n. Вероятность d_n = P_n(D_n) события D_n, состоящего в том, что данная перестановка является полной, равна 0 при n = 1 и равна

1.-1. + ... + ^-L (8.4)

при n > 1 (следствие: lim d_n = -).

Задача о значении d_n широко известна как задача о шляпах. На собрание, состоявшееся поздно вечером, n его участников пришли в шляпах и оставили их в раздевалке, а когда собрание окончилось, разобрали шляпы наугад в темноте (в раздевалке перегорела лам­почка) и разошлись по домам. Какова вероятность того, что каждый пришел домой в чужой шляпе?

Указание. Для любого r такого, что СЩЩn, можно рассмотреть ве­роятность p (n, r) того, что перестановка длины n имеет ровно r непо-

Задачи

69

движных точек (ровно г человек пришли домой в своих шляпах). То­гда р(п,0) + р(п, 1) + ... +р(п,п) = 1. Далее надо доказать, что р(п,г) =

= (")-, г— тР(" - г, 0) = -р(п - г, 0), откуда будет следовать, что

г пуп- 1)...(п -г) г!

^d„ + Y[dn-! + ^„-! + ... + (_-TjA-! + ^do = 0.

С учетом d₀ = 1 последнее соотношение однозначно определяет все d_t,d₂, ... Остается убедиться, что подстановка значений (8.4) в левую часть этого со­отношения дает 0. Подставляя т-77 + ?7-о7 + --- + i^, r = °> *> •••> ^п, в левую часть этого соотношения, получим J] ^- .^ (роль г играет п - j).

Слагаемые этой суммы можно перегруппировать так, чтобы внутри группы значение i+j было постоянной величиной I. Это даст

ZjZj (Z-i)!i! Z_iJ! Zj (Z-i)!iP ' '

!=0 i=0 г=о ;=o

последний шаг доказательства очевиден.

32. При быстрой сортировке (в любом из рассмотренных ее ва­риантов) число пар индексов (i,j), попадающих в стек отложенных заданий, не превосходит длины п исходного массива.

32. Верно ли, что определение усредненных затрат некоторого рандомизированного алгоритма требует задания распределения ве­роятностей

а) на множестве всех допустимых входов?

б) на каждом из множеств всех входов фиксированного размера?

34. Если измерять затраты рандомизированной быстрой сортиров­ ки количеством обращений к генератору случайных чисел, то слож­ ность этой сортировки есть величина порядка п. То же самое верно, если в определении функции затрат вместо математического ожида­ ния взять максимум затрат по соответствующим сценариям.

35. Идея, лежащая в основе быстрой сортировки, может быть использована для нахождения rn-го наименьшего элемента среди а_ъа₂,...,а_п,1^т^п (самый маленький элемент—это 1-й наимень­ ший, следующий элемент —2-й наименьший и т.д.). Разбиение мас­ сива с использованием случайно выбранного разбивающего элемента порождает два массива длины i - lиn - i при некотором 1 ^ i ^ п. Ес­ ли т = i, то поиск закончен, если т ^ i - 1, то далее рекурсивно нахо­ дится т-й наименьший в первом массиве, а если т > i, то рекурсивно находится (т - 0-й наименьший во втором массиве. Можно ввести сложность по числу сравнений при рассмотрении двух параметров

70