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

Сортировка и конечные вероятностные пространства.

От

7г(2^т) ~ . —, т—>оо₅ а также равенством V{m) = п{2^т) - п{2^т-^г), получим

Теперь уже экспоненциальность роста сложности в среднем алго­ритма пробных делений выводится легко. Обозначим через D{n) количество делений, требующееся алгоритму пробных делений при­менительно к натуральному числу п. Для любого простого р ^ ^ 2^т-^г, т^7, выполнено D{p) > 2^т1^^х (в самом деле, D{p) = LV p J - 1 Z L2^(m -^{1) / 2}J - 1 > 2&"-«/ ² - 2, и при т ^ 7 выполнено

; m -l) / 2 ПШ / 2-1 ТЛ

2^т — 1 на ^гт 2 D{n). При ^т ^ 7 мы имеем

2^{(m 1) / 2} - 2 ^ 2^{т12 г}). Интересующая нас сложность в среднем рав-1

= 2Г71-1 2^т-1

Т.	D(n)^	ГП-1		Т.
=2т-1			2 ^mp	-Чр < 2^т— простое

_2т_₁ „,! D{p)^V{m)2-^ml2. (5.5)

2ГП-1

Учитывая (5.4), находим, что последняя величина при т —»оо асимп­тотически равна

1 от / 2

(21п2)т '

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

Это говорит о том, что исследуемая сложность по числу делений

в среднем есть Г2(— 2^m/2 ) и как функция от m эта сложность не мо- m

жет быть оценена как O{m^d) ни при каком d eN.

Определение 5.2. Вещественная неотрицательная функция f (m), определенная для целых положительных значений аргумента, назы­вается полиномиально ограниченной, если существует полином P{m) с вещественными коэффициентами такой, что f{m)^P{m) для всех m eN⁺. (Очевидно, что мы получим эквивалентное определение, если дополнительно потребуем, чтобы все коэффициенты полинома P{m) были неотрицательными; другие эквивалентные варианты определе­ния: f{m) = O{m^d) для некоторого d eN и f (m) = m^{O (1)}.)

Доказанное нами можно сформулировать так:

Пусть в качестве размера входа алгоритма пробных делений, пред­назначенного для распознавания простоты натурального числа n, привлекается m = А(n). Тогда временные сложности этого алгоритма как в худшем случае, так и в среднем по числу делений не являются полиномиально ограниченными функциями от m.

Краткое обсуждение идеи такого алгоритма распознавания про­стоты числа, который имеет полиномиально ограниченную слож­ность в худшем случае (тем самым, разумеется, и в среднем), бу­дет проведено в примере 22.2. При этом речь пойдет не об алгеб­раической сложности по числу делений, мультипликативной сложно­сти и т. д., а о битовой сложности, что приводит к существенно более сильным утверждениям. До этого в гл. 5 будет детально рассмотрено само понятие битовой сложности.

При рассмотрении сложности в среднем мы, прежде всего, должны превратить каждое из множеств входов, обладающих фиксированным размером, в вероятностное пространство. Проще работать с конеч­ными вероятностными пространствами, но как обходиться такими пространствами, имея дело, например, с алгоритмами сортировки, входом каждого из которых, при фиксированном размере n, может быть любой массив x_г,x₂, ■■■,x_n с попарно различными элементами? Общий принцип заключается в том, что мы разбиваем все имеющие фиксированный размер n входы на некоторые классы, включая в один

§ 6. Сортировка и конечные вероятностные пространства 47

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

На выполнение любой сортировки с помощью сравнений сами значения элементов х ₁, х₂,...,х_п не оказывают никакого влияния, ва­жен лишь их относительный порядок. Поэтому в один класс есте­ственно объединять все массивы х ₁, х₂,...,х_п, имеющие один и тот же порядок элементов по отношению друг к другу. Такой класс мо­жет быть представлен перестановкой чисел 1, 2,...,п с соответству­ющим порядком элементов (перестановкой длины п). В дальнейшем для любого n eN* мы будем рассматривать функцию i/>„, аргумента­ми которой являются любые попарно различные числа х ₁, х₂,...,х_п, а значением — перестановка а = (а₁,а₂,..., а_п) чисел 1, 2,...,п, отра­жающая относительный порядок чисел х ₁, х₂,...,х_п. Например,

1/>3 (-³₄, -10,17) = (2,1, 3). (6.1)

Множество всех перестановок чисел 1,2,..., п будет обозначаться че­рез П„, так же будет обозначаться и вероятностное пространство,

получаемое приписыванием вероятности — каждой из этих переста­новок.

Рассмотрим некоторые события в вероятностном пространстве П_п;

вероятность каждого из них, очевидно, будет равна —, где М—чис­ло перестановок, составляющих событие. Эту вероятность мы будем обозначать через P_п(-).

Пример 6.1. Начнем с события B^v_n, 1^v^n, состоящего в том, что v -й элемент a_v перестановки (а₁,а₂,...,а_п) равен v. Перестанов­ку (а₁,а₂,...,а_п)&и_п можно рассматривать как отображение множе­ства {1,2,...,п} на себя, при котором 1 переходит в а₁, 2 переходит в а₂ и т.д., и событие B^v_n состоит тогда в том, что v является непо­движной точкой перестановки. Множество, состоящее из перестано­вок (а₁,а₂,..., а_п) таких, что a_v=v, содержит (п-1)! элементов, от-

_nv (п^-1)! 1
сюда P (В„) = ---------:— = - при всех рассматриваемых v.

В зависимости от выбранной перестановки число неподвижных точек может быть любым целым из диапазона от 0 до п. Рассмотрим

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

вопрос о среднем числе неподвижных точек перестановок длины n: найдем математическое ожидание определенной на Π _n случайной ве­личины ξ_n, равной числу неподвижных точек перестановки a. Допол­нительно определим случайные величины

_v 1, если a_v = v, ζ =

0, если a_v = v,

v = 1, 2,..., п. Мы видим, что P_П (С„ = 1) = P_П (В^) = -, откуда E<^ = - и

E£_п = E (C ¹ + Й +... + О = Ц 1 + EЙ +... + EГ = п • -= 1.

Итак, среднее число неподвижных точек равно 1.¹ Неподвижные точки перестановки соответствуют элементам мас­сива, которые при сортировке не нуждаются в перемещениях на дру­гие места, они и так находятся именно там, где должны находиться, и это может использоваться в некоторых видах сортировки (см. за­дачу 25).

Найдем теперь вероятности еще трех событий — эти вероятности потребуются нам при исследовании сложностей в среднем некоторых сортировок.

Предложение 6.1. Пусть п е N+. Тогда (i ) при 1 s= и s= п, 1 s= v s= п имеем

■

" " п

для события F^^v, состоящего в том, что v- u элемент перестановки (а₁,а₂,...,а„) равен и;

(ii) при 1 < и ^ п и любой перестановке р чисел 1, 2,..., и - 1 имеем

" (") (и-1)!

Э ля события G ^ ^p, состоящего в том, что относительный поря Э ок элементов а,-, а,-,..., а,- перестановки ( а-,, а₂,... а„), меньших и, сов-

¹1 ¹2 'ii-1 ^1У, ⁿ ^

падает с относительным порядком элементов заданной перестанов­ки р (аналогичное утверждение имеет место для элементов, боль­ших и);

(iii) npu0^u<v^n имеем

P„ (Я^¥) = -
" n _v

¹ Серия вероятностных «задач о совпадении» с решениями приведена в [27].

§ 6. Сортировка и конечные вероятностные пространства 49

для события H_n^{u v}, состоящего в том, что в перестановке {a_ъa₂,...,a_n) содержится u элементов a_i, 1 ^ i < v, для которых a_i <a_v.

Доказательство. (i) Множество перестановок { a _ъ a₂,..., a_n) таких, что a_v = u, содержит (n -1)! элементов, независимо от значений u и v.

(ii) Событие G_n^u'^p включает ( ⁿ J(n - u + l)! перестановок, т.е.

n!
------ гту перестановок, независимо от вида p.

(iii) Очевидно, что если p —любая перестановка чисел 1, 2,..., v, то множество перестановок {a_г,a₂..., a_n) таких, что 'ф_v{a₁, a₂, ■■■,a_v) =

= p, содержит (ⁿ)(n - v)! = ⁿ_v - элементов (мы используем функ­цию i/ v, определенную перед формулой (6.1)). Заметим, что коли­чество тех перестановок p чисел 1, 2,..., v, в которых последний эле­мент равен u + 1, есть (v -1)!. Поэтому количество перестановок,

образующих событие H_n^{u v}, равно ^j(v -l)!, т.е. у, откуда следует
требуемое. _v ' _v □

Напомним полезную формулу из курса теории вероятностей. Как и прежде, мы ограничимся рассмотрением конечных вероятност­ных пространств элементарных событий. Пусть W — такое простран­ство, P — соответствующее распределение вероятностей, Е, —некото­рая случайная величина (функция) на W. Пусть события W _ъ W₂,..., W_l задают полную группу событий, т. е. эти события попарно несовмест­ны и

W = W₁+W₂ +... + W_l. (6.2)

Представление W в виде (6.2) с помощью некоторой полной группы событий мы будем называть разложением W. Как обычно, E? —это значение ^?(w)P(w), т. е. математическое ожидание (или среднее)

случайной величины £, а E(£| W_k), k = 1, 2,..., l, суть соответствующие условные математические ожидания этой случайной величины (при условии осуществления события W_k). Тогда, как известно, имеет ме­сто формула полного математического ожидания:

^l
E? = ^E (? | W УP (W У. (6.3)

k =i

Оценивание математических ожиданий является оцениванием число­вых сумм. В этом иногда помогает простой прием, описанный в при­ложении B.

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

Пример 6.2. Исследуем сложности в среднем по числу сравне­ний и перемещений сортировки простыми вставками, которую, как и прежде, мы будем рассматривать в двух вариантах \_г и 1₂ (см. при­мер 1.4). Вначале займемся первым вариантом \_г этой сортировки, полагая затраты равными числу сравнений. Входные массивы счита­ем перестановками чисел 1,2,..., п. Для исследования сложности по числу сравнений введем случайные величины Е}_п, С •••> Ъ^п-^г, опреде­ленные так, что значение Е,¹_п для

а=(а₁,а₂,...,а_п)∈П„

равно затратам на i -м шаге нашей сортировки, применяемой к а. Ясно, что интересующее нас математическое ожидание есть Е(^ + ^ +... +CJJ-¹), и

7}_i(n) = E^ + E?2 +... + Eq-¹. (6.4)

Найдем ?_п, l^i<n. Рассматривая события H*-^l+1, fc = 0, l,..., i, об­разующие разложение пространства П„, и применяя формулу (6.3) полного математического ожидания, мы имеем согласно предложе­нию 6.1(iii)

ЕГ=ДтУЕ(Г|Я^⁺¹). (6.5)

fc=0

Если перестановка а = {а_ъа₂,...,а_п) принадлежит событию Н^+, то в этой перестановке перед элементом a_i+1 имеется ровно к элементов, меньших его, и, очевидно,

._f i -fc + l, если/с > 0,
n~i, если/с = 0.

Мы видим, что при выполнении события H ^^I+1 значение Е,¹_п опреде­лено однозначно (напомним, что значение E,^l_n, i = 1, 2,..., п - 1, равно числу сравнений на i -м шаге, а перед выполнением i -го шага элемен­ты a₁,a₂,...,a_i уже упорядочены по возрастанию). Поэтому

. _м+1 f i -fc + 1, если/с > 0,
" "' i, если fc = 0.

В соответствии с (6.5)

fc=i

§ 6. Сортировка и конечные вероятностные пространства 51

Используя (6.4), получаем выражение

п-1 +

п-1 f i

2 i + l

i = l

для искомой сложности в среднем. С помощью известной из матема­тического анализа формулы (ее вывод имеется в приложении B)

Дата добавления: 2014-01-11