21. [НМЗО] Найдите производящую функцию для последовательности (п!> и исследуйте свойства этой функции.

22. [М21] Найдите производящую функцию G(z), для которой

23. [МЗЗ] (Л. Карлитц (L. Carlitz).) (а) Докажите, что для всех целых чисел m > 1 существуют многочлены fm{z\,... ,Zm) VL gm{zi,... ,Zm), такие, что формула

1. .fcm>0

превращается в тождество для всех целых чисел п > г > 0.

(b) Обобщая упр. 15, найдите замкнутую форму для суммы

выразив ее через функции fm и Qm из п. (а).

(c) Найдите простое выражение для Sn{zi,..., Zm), если zi = = Zm = z. 24. [M22] Докажите, что для любой производящей функции G{z)

Y{")[z-]G{zt = [zn{l + zGiz)r.

Вычислите обе части этого тождества, если G{z) равна, (а) 1/(1 - z); (Ь) (е" - l)/z. ► 25. [М23] Вычислите сумму 13*, (fc)(Ifc)(~2)*, упростив эквивалентную формулу Е,К](1-2«;Г [z"-]{l+zf"-.

26. [М40] Найдите обобщение обозначения (31), согласно которому можно, например, записать [z - 2z] G{z) - а2 - 2аь, где G{z) задается формулой (1).

1.2.10. Анализ алгоритма

Пришло время применить некоторые методы, рассмотренные в предыдущих разделах, к изучению типичного алгоритма.

Алгоритм М {Нахождение максимума). Для заданных п элементов Х[1], Х[2],..., Х\п] необходимо найти такие величины т и j, что т = X[j] = maxi<,<„ Х[г], где j - наибольший индекс, удовлетворяющий этому соотношению. Ml. [Инициализация.] Положим j гг, гг -1, т <- Х[п]. (Во время вьшолнения алгоритма будем иметь тп = X[j] - тах*;<г<„ X[i].)

М2. [Все проверено?] Если fc = О, то работа алгоритма заканчивается. МЗ. [Сравнение.] Если A"[fc] < m, перейти к шагу М5.

М4. [Замена т.] Положим j fc, m Х[к]. (Это значение т является новым текущим максимумом.)

М5. [Уменьшение fc.] Уменьшим fc на единицу и вернемся к шагу М2.

Может показаться, что данный алгоритм настолько тривиален, что его вообще не стоит подробно анализировать. Но на самом деле это хороший.пример, показывающий, как можно исследовать более сложные алгоритмы. Анализ алгоритмов имеет

Инициализация

7>с

Рис. 9. Алгоритм М Подписи к стрелкам показывают, сколько раз осуществляется проход каждого пути Заметьте, что должен выполняться первый закон Кирхгофа, который в данном случае выглядит так: число входов в каждый узел должно равняться числу выходов из него.

очень большое значение в программировании, потому что, как правило, существует несколько алгоритмов решения конкретной задачи и необходимо знать, какой из них наилучший.

Для алгоритма М требуется фиксированный объем памяти, поэтому будем анализировать только время, необходимое для его выполнения. Для этого подсчитаем, сколько раз вьшолняется каждый шаг (рис. 9).

Номер шага Количество выполнений Ml 1

М2 «

МЗ п-1

М4 А

М5 п-1

Зная, сколько раз вьшолняется каждый шаг, можно определить время работы алгоритма на конкретном компьютере.

В приведенной выше таблице неизвестна только величина А, которая определяет, сколько раз необходимо изменить значение текущего максимума. Чтобы довести анализ до конца, исследуем эту любопытную величину А.

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

Минимальное значение А равно нулю; это будет в случае, если

Х[п] = max Х[к].

1<к<п

Максимальное значение А равно гг - 1; это будет в случае, если

Х[1]>Х[2] > ••• >Х[гг]. Таким образом, среднее значение лежит между О и гг - 1. Будет ли это п? Или \Аг? Чтобы ответить на поставленный вопрос, нужно выяснить, что понимается под средним. А чтобы правильно определить среднее, сделаем некоторые, предположения, касающиеся характеристик входных данных Х[1],Х[2]-,Х[п]. Будем считать, что Х[к]-различные значения и что все п1 перестановок этих значений равновероятны. (В большинстве случаев это разумное допущение, но.

как вы увидите из упражнений к данному разделу, анализ можно проводить также, исходя из других предположений.)

Производительность алгоритма М не зависит от самих величин Х[к]; имеет значение только относительный порядок их расположения. Например, если п = 3, предполагается, что следующие шесть возможностей равновероятны.

Ситуация Значение А Ситуация Значение А

Х[1] < Х[2] < Х[3] О Х[2]<Х[3]<Х[1] 1

Х[1] < Х[3] < Х[2] 1 Х[3] < Х[1] < Х[2] 1

Х[2] < Х[1] < Х[3] О Х[3] < Х[2] < Х[1] 2

Среднее значение А при п = 3 равно (О+ 1 + 0+1 + 1 +2)/6 = 5/6.

Очевидно, что можно считать Л[1],Х[2],... ,Х[п] числами 1,2,...,п, расположенными в определенном порядке. Согласно нашим предположениям все п! перестановок равновероятны. Вероятность того, что А имеет значение к, равна

p„j. = (число перестановок п объектов, для которых А = к)/п\. (1)

Для нашего примера (см. таблицу выше) рзо = , рз1 = , рз2 = .

Среднее значение (или просто среднее) определяется, как обычно, по формуле

Дисперсия V„ определяется как среднее значение величины (Л - Л„)2, поэтому Vn = Y{k - Anfpnk = YI P"* - 2 X] Рггк + Al YPrk

к к к к

= Y -2AnAr.+Al = Y »* - • (3)

И наконец, среднее квадратичное отклонение а„ определяется как \/V.

Чтобы разъяснить смысл характеристики (т„, заметим, что для всех г > 1 вероятность того, что значение А не попадает в промежуток (Л„-Г(т„, Л„+Г(т„), не превышает l/r. Например, событие \А - Л„ > 2(т„ происходит с вероятностью < 1/4. {Доказательство. Пусть р - требуемая вероятность*. Тогда если р > 0. то среднее величины (Л - Л„)2 больше, чем р {гспУ + (1 - р) О, т. е. V„ > prVn-) Обычно это соотнощение называют неравенством Чебышева, хотя на самом деле оно было впервые получено Ж. Бьенэме (J. Bienayme) [Comptes Rendus Acad. Sci. Paris 37 (1853), 320-321].

Чтобы определить поведение Л, найдем вероятности р„к- Это легко сделать методом индукции. Со1ласно (1) нужно подсчитать число перестановок н аяементов, для которых А = к. Обозначим это число через Рпк- Оно равно Рпк = п\рпк-

Рассмотрим перестановки xiX2 ---Хп эле.ментов {1,2,...,п} (см. раздел 1.2.5). Если Xl = п, то значение Л на единицу больше, чем значение для перестановки Х2--Хп- Если же Xl ф п, то значение Л является точно таким же, как для перестановки Х2---Хп. Следовательно, Рпк = P(n-i)(k-i) + {п - l)P(n-i]k, что эквивалентно соотношению

Рпк = -Р(п-1)(к-1) + -Р(п-1)к- (4)

* р = Р{\А - Ап\ > 2(Тп). - Прим. ред.