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

Указание. Предположение о том, что V(m) < 2^3m/4 для всех т > т₀, позво­лило бы, исходя из равенства

я(2^т) = я(2^т°) + У(т₀ + 1) + У(т₀ + 2) + ... + V(m),

вывести верхнюю оценку я(2^ш) = 0(2^3ш/4), что вступило бы в противоре-

от

чие с неравенством я(2^т)>с— с положительной константой с. Поэтому существует последовательность тп₁ <гп₂ < ... натуральных чисел таких, что V(m_;) > 2^3m'^/4, i = l,2, ... Можно рассмотреть (5.5) для тп = тп₁,тп₂, ...

25. Сложность по числу перемещений (обменов) в среднем для сортировки выбором при условии, что мы исключаем обмены вида

x_t<—*Хъ, не превосходит п - 2 + -, где п—длина массива.

п

Указание. В перестановках из П_п среднее число элементов a, l^i^n-1,

таких, что a_t=i, есть (см. пример 6.1).

п

26. Найти среднее число присваиваний m := ... при выполнении алгоритма поиска наименьшего элемента массива:

тп:=х₁;

for i = 2 to п do

if Xi<m then т:=х_; fi od

Предполагается, что все возможные взаимные порядки элементов в исходном массиве длины п являются равновероятными; в качестве размера входа берется п.

Указание. Рассмотреть разложение всего вероятностного пространства в сумму двух событий: последний элемент исходного массива является его наи­меньшим элементом (вероятность равна -) и соответственно последний эле-

п мент исходного массива не является его наименьшим элементом (вероят­ ность равна ). Пусть s(n) обозначает искомое математическое ожидание.

п Показать, что условное математическое ожидание исследуемого числа при­сваиваний, соответствующее первому событию, есть s(n- 1) + 1, а условное математическое ожидание, соответствующее второму событию, есть s(n - 1). Пользуясь формулой полного математического ожидания, вывести отсюда ре­куррентное соотношение для s(n) и найти его решение, удовлетворяющее условию 5(1) = 1.

27. Пользуясь дискретным аналогом формулы Ньютона—Лейбни-

п

ца, согласно которому £ (/№ + 1) - /№)) = /(" + 1) - /(1), вычис-

fc=i

лить сумму 2 ттт.—Тл, входящую в (7.3).

Задачи

67

28. Исходя из (7.3), пользуясь приемом оценки сумм из прило­жения B и результатом из предыдущей задачи, доказать неравен­ство Гд₅(п) ^2nlnn, из которого будет следовать, что величина 0{п) в правой части (7.4) отрицательна.

28. Вернемся к задаче 8. В качестве алгоритма с указанными свой­ствами можно предложить следующий: при наличии вагонов на пра­вой стороне узла к операции В прибегаем лишь тогда, когда на ле­вой стороне невозможно увеличить на 1 число вагонов с правиль­ным чередованием цветов с помощью какой-то из операций МИМО и ИЗ; в остальных случаях выполняется одна из операций МИМО и ИЗ, если возможны обе, то первая из них. Как и в задаче 8, счи­таем, что черных и белых вагонов по п штук, и п — размер входа. Какова сложность по числу сортировочных операций этого алгорит­ма в среднем?

Указание.^г Можно доказать следующие три утверждения.

1. Предположим, что в исходном расположении первый вагон на правой стороне белый. Тогда число сортировочных операций, требующихся алгорит­му, равно Зп - к, где к есть количество максимальных сплошных последо­вательностей черных вагонов в исходном расположении (непосредственно слева и справа от каждой такой сплошной последовательности нет черных вагонов, таков смысл «максимальности»).

1. Вновь предположим, что в исходном расположении первый вагон на правой стороне белый. Тогда количество исходных расположений, в которых имеется ровно к максимальных сплошных последовательностей черных ва­гонов, есть ( J ( J.

3) ^-п-1^п-1 = 2^п-2 ,~,n-k к п

й в ^П-(п-к)^ПП-¹

=

_к=1 n-k к п

Из первых двух утверждений выводится, что искомая сложность в сред­нем есть

2n + 2 • — =

f 2л Л

п

третье утверждение позволяет получить из этого, что интересующая нас

n(5n-3) 5 1

сложность есть — — = -п +

L = П + -+о(1).

30. (Задача не связана со сложностью в среднем, но приводит к ре­куррентному соотношению, которое решается сходно с (7.2).) Дока­зать, что для любого Z > 0 можно, не применяя клей, построить из костяшек домино, длина каждой из которых равна 2, навес длины Z

Решение принадлежит А.П.Фокину.

68