§ 8. Функция затрат рандомизированного алгоритма

61

которых не превышает n - 1, при этом не исключается равенство нулю одной из длин. С каждой из двух полосок разрезальщик про­делывает ту же операцию, получая вознаграждение в соответствии с тем же принципом оплаты. Каково математическое ожидание раз­мера вознаграждения, получаемого разрезальщиком за всю работу? Здесь при фиксированном n множество всех возможных сценари­ев (будем называть их n-сценариями) — это фактически множество

3

3

3

3

3

0

0

0

0

1

0

1

1

0

1

Рис. 9. Сценарии разрезания полоски из трех клеток (3-сценарии).

некоторых двоичных деревьев; на рис. 9 показано одно из возмож­ных представлений множества всех 3-сценариев. В каждой вершине дерева записывается число клеток в полоске. При произвольном n ^ О понятие п-сценария определяется рекурсивно: О-сценарий и 1-сце-нарий—это одна вершина, которой приписа­но число 0 или соответственно 1; пусть п > 1,

тогда любой n-сценарий s получается выбо- i - 1 / \ n - i

s'

с"

Рис. 10. Структура п-сценария.

ром некоторого числа i, 1 ^ i ^ п, некоторого (i - 1)-сценария s' и некоторого (п - О-сцена-рия s": из корня п исходят ребра к вершинам i-1 и n-i, к которым подклеиваются корни

сценариев s' и s" (рис. 10). Каждому п-сцена-

рию s естественным образом приписывается

вероятность P„(s) (здесь индекс п указывает

на то, что вероятность соотнесена с некоторым n-сценарием): если

п = 0 или п = 1, то сценарии имеют вероятность 1, а при п > 1

P_n(s) = -Pi_₁(s^/)P„-i(s^/0-

(8.1)

Например, третий из 3-сценариев, изображенных на рис. 9, имеет вероятность ^, каждый из остальных—вероятность -т.

Формула (8.1) отражает идею алгоритма, а именно что после опре­деления i выбор (i - 1)-сценария s' и выбор (п - О-сценария s" неза­висимы друг от друга. Эта формула превращает множество всех п-сце-нариев при фиксированном п в вероятностное пространство S„. Поль-

62

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

зуясь индукцией по п, проверим, например, что ^ P_n(s) = l: при п = 0 и п = 1 это очевидно, при п > 1 имеем

seS„ i = l s'eS_-j

s"eS

■i-1

*n-i

Yj((Yj Pi-^s'A J] Pn-its"A

i = l s'eSj_-j s"<ES_n-i

- P _--msm P-iLSJ=- 1-1 = 1.

i=l

Плата за разрезание полоски длины п на отдельные клетки полно­стью определяется использованным n-сценарием, это задает случай­ную величину Хп на S_n, и нас интересует математическое ожидание этой величины. Для сценария s, представленного на рис. 10, мы на­зовем s' и s" левым и правым подсценариями. При п > 1 определим на S_n дополнительно к j_n еще две случайные величины %'_п и %'^, поло­жив ^(s) = Xi-i(.s') и x'nte) = Xn-i(s"\ где s' и s" суть левый и правый под сценарии сценария s. Имеем при п > 1

j_n(s) = n-l + ^(s)+^'(s). Пусть п > 1. Введем разложение

s_n=s^ + s;; + ...+s;;, (8.2)

где S^—это событие «левый подсценарий данного n-сценария являет­ся (i - 1)-сценарием (и соответственно правый подсценарий является (n-0-сценарием)», i = l,2,...,n. Очевидно,

P_n(S¹_n) = P_n(S²_n) = ... = P_n(Sⁿ_n) = ±,

поэтому по формуле полного математического ожидания получаем

Л/1 ^_| ««' П'_п

1=1

п

1 + ^ ^ (E(^IS^) + Edr^'ISi,)) =

-1 + -У(Eу/-1 + Eг_п-Л

i=i

п

1 + - У Eг_г-1 = п - 1 + - У Er_fc.

=п-1+-п

= П

П

1=1

п п-1

= п-1 + -У Eг,₁ = п ²

i=l fc=o

i=i