AOP_Tom1 (1021736), страница 28
Текст из файла (страница 28)
[Мйд] Докажите, что для любой производящей функции С(з) ~ '(™)[" "]с( )'=[."]( + а( )) . з Вычислите обе части этого тождества, если С(з) равна. (а) 1/(1 — з); (Ь) (е* — 1)/а ь 2б. [Мйд] Вычисните сумму 2; ("„) (~„"~")(-2)», упростив эквивалентную формулу [,„Я] (1 2щ) [з — ](1+ з) 26. [М40] Найдите обобщение обозначения (31), согласно которому можно, например, записать [з~ — 2з~] 0(в) = аз — 2ам где С(з) задается формулой (1).
1.2.10. Анализ алгоритма Пришло время применить некоторые методы, рассмотренные в предыдущих разделах, к изучению типичного алгоритма. Алгоритм М (Нахождение максимума). Для заданных и элементов Х[1], Х[2],..., Х[п] необходимо найти такие величины т и 1, что пт = Х[Я = шах1<,<„Х[1], где д — наибольший индекс, удовлетворяющий этому соотношению. М1. [Инициализация.] Положим/ < — н, /с ~ — и — 1, ш < — Х[п].
(Во время выполнения алгоритма будем иметь т' = Х[Я = шаха<,<„Х[1].) М2. [Все проверено?] Если й = О, то работа алгоритма заканчивается. МЗ. [Сравнение.] Если Л [Ь] < гп, перейти к шагу Мб. М4. [Замена гп.] Положим 1 < — /с, гп ~ — Х[Й]. (Это значение т является новым текущим максимумом.) Мб. [Уменьшение я.] Уменьшим /с на единицу и вернемся к шагу М2. з Может показаться, что данный алгоритм настолько тривиален, что его вообще не стоит подробно анализировать. Но на самом деле это хороший, пример, показывающий, как можно исследовать более сложные алгоритмы, Анализ алгоритмов имеет Рис. 9. Алгоритм М Подписи к стрелкам показывают, сколько раэ осуществляется проход каждого пути Заметьте, что должен выполняться первый закон Кирхгофа, который в данном случае выглядит так: число входов в каждый узел должно равняться числу выходов иэ него.
очень большое значение в программировании, потому что, как правило, существует несколько алгоритмов решения конкретной задачи и необходимо знать, какой из них наилучший. Для алгоритма М требуется фиксированный объем памяти, поэтому будем анализировать только время, необходимое для его выполнения. Для этого подсчитаем, сколько раз выполняется каждый шаг (рис.
9). Номер шага М1 М2 МЗ М4 М5 Количество выполнений 1 гг и — 1 Я и — 1 Зная, сколько раз выполняется каждый шаг, можно определить время работы алгоритма на конкретном компьютере. В приведенной выше таблице неизвестна только величина А, которая определяет, сколько раз необходимо изменить значение текущею максимума. Чтобы довести анализ до конца, исследуем эту любопытную величину А. Этот анализ обычно заключается в нахождении минимального (для оптимистов), максимального (для пессимистов), среднего (для специалистов по теории вероятностей) значения А и его среднего квадратичного отклонепоя (данная характеристика показывает, насколько близким к среднему может оказаться значение). Минимальное значение А равно нулю; это будет в случае, если Х[п] = шах Х[/с].
1<э<а Максимальное значение А равно и — 1; это будет в случае, если Л [1] > Л [2] » . Х[п]. Таким образом„среднее значение лежит между 0 и и — 1. Будет ли это |п? Или тггп? Чтобы ответить на поставленный вопрос, нужно выяснить, что понимается под средним.
А чтобы правильно определить среднее, сделаем некоторые предположения, касающиеся характеристик входных данных Л [Ц, Л"[2]...., Х[п]. Будем считать, что Х[(г] — различные значения н что все и! перестюювок этих значений равновероятны. (В большинстве случаев это разумное допущение, но, как вы увидите из упражнений к данному разделу, анализ можно проводить также, исходя из других предположений.) Производительность алгоритма М не зависит от самих величин Х[гг]; имеет значение только относительный порядок их расположения. Например, если и = 3, предполагается, что слечующие шесть возможностей равновероятны.
Ситуация Значение А Ситуация Значение А Х[Ц < Х[2) < Х[3) О Л [2] < Х[3] < Х[Ц 1 Л[Ц < Х[3) < Х[2) 1 Л [3] < Х[Ц < Х[2] 1 Х[2) < Х[Ц < Х[З) О Х[3] < Х[2] < Х[Ц 2 Среднее значение А при п = 3 равно (О + 1+ О+ 1+ 1+ 2)/6 = 5/6. Очевидно, что можно считать Л" [Ц, Л[2],..., Х[п) числами 1,2,...,и, расположенными в определенном порядке. Согласно нашим предположениям все и! перестановок равновероятны. Вероягпносгпь того, что .4 имеет значение й, равна рпь = (число перестановок и объектов, для которых А = й)/и!. для нашего примера (см. таблицу выше) Рзо = 5, Рзг = г Рзт = в.
Среднее значение (или просто среднее) определяется, как обычно, по формуле Ап гп ~~г ггрпь. (2) ь Дисперсия Ъ'„определяется как среднее значение величины (А — Ап)з, поэтому 1п = ~~~,((с — -4п) Р»ь = ~й Рпь — 2 4»~~~ Ь ы+ 4п г Рпь ь ь ь ь = ~К Рпь — 2АпАп+А„= ~~г Ь рпь — А„. (3) ь ь И наконец, среднее квадратичное отклонение оп определяется как ~ГР„.
Чтобы разъяснить смысл характеристики оп, заметим, что для всех г > 1 вероятность того, что значение А не попадает в промежуток (Ап-гоп, А»+гоп), не пРевышает 1/гг. НапРимеР, событие [А —,1»[ > 2вп пРоисходит с веРоЯтностью < 1/4. (Доказагаельство. Пусть р — требуемая вероятностьп. Тогда если р > О. то сРеднее величины (А — Ап)т больше. чем Р (гтп)т+ (1 — Р) О, т. е. 1» > РггК,.) Обычно это соотношение называют неравенством Чебышева, хотя на самом деле оно было впервые получено Ж.
Бьенэме (3. Вгепауще) [Сотргев Вепдив Асад. Ясй Рвпв 37 (1853), 320 — 32Ц. Чтобы определить поведение А, найдем вероятности рпы Это легко сделать методом индукции. Сог ласйо (1) нужно подсчитать число перестановок гг элементов, для которых А = 1г. Обозначим это число через Рпгп Оно равно Рпь = и! Рпы Рассмотрим перестановки хгха... хп элементов [1, 2,..., и) (см. раздел 1.2.5).
Если хг = и, то значение А на единицу больше, чем значение для перестановки хг...хп. Если же хг ф п, то значение А является гпочно таким же, как для перестановки хт...хп, Следовательно, Рпь = Рг„гць г~ + (и — 1)Рг„ггы что эквивалентно соотношению 1 и — 1 Рпг< Р(п — гдгг г) + Р( — 1 гг' гг н * Р = Р(]Л вЂ” А„~ > 2»„).— ПРим.
Ред. (4) О 1 2 3 4 5 6 7 В 9 10 11 Рис. 10. Распределение вероятностей для шага М4 прн и=12 Среднее равно 58301/27720, т е приближенно равно 2.10. Дисперсия приближенно равна 1 54 По этой формуле можно найти р„ы если задать начальные условия: Ры = 5оь; рбя = О, если й < О (5) Теперь можно исследовать величины ряь с помощью производящих функций. Пусть С„( ) = -С„г( )+ С„1( ) = С, ( ).
и и и (7) (Читателю следует внимательно исследовать связь между соотношениями (4) и (7).) Теперь мы видим, что с+и — 1 э+и — 1 э+и — 2 и — 1 1 = †(г + и — 1)(г + и — 2)...(з + 1) и! (8) Таким образом, С„(г) — это, в сущности, биномиальный коэффициент! Рассматриваемая здесь функция уже встречалась в предыдущем разделе (соотношение 1.2.9-(27)), где мы получили (,) ~;- [и1,4-1 ь Следовательно, р„ь можно выразить с помощью чисел Стирлинга: Рпг = [й ~/ий (9) На рис. 10 показаны приближенные значения рвь при и = 12. г 'н(х) 'Рно+Рпгс+ ' ' ' = ~~~ Рпьг (6) Известно, что А < и — 1, поэтому р„ь = О для больших значений й Таким образом, функция б„(в) — это на самом деле многочлен, хотя для удобства она и представлена в виде бесконечного ряда Из (5) получаем, что С1(г) = 1, и согласно (4) Теперь остается только подставить значение р„а в (2) и (3) и получить нужную среднюю величину.
Но зто легче сказать, чем сделать. На самом деле очень редко удается явно определить вероятности рпю В большинстве задач будет известна производящая функция Сп(а), но не сами значения вероятностей. Важно то, что можно легка определить среднее и дисперсию по гамой производящей функции. Чтобы понять, как зто делается, предположим, что имеется производящая функция, коэффициенты которой представляют собой некоторые вероятности; С(а) = ро + Р1 а + Рта + Здесь ре — вероятность того, что некоторая случайная величина принимает значение )с.
Вычислим величины* шеап(С) = ~ )сры наг(С) = ~~ )с~ре — (гпеап(С)) (10) л Это нструдно сделать с помощью операции дифференцирования. Заметьте, что С(1) = 1, (11) гак как С(1) = ро+рз+рз+. — сумма всех возможных веронтностей. Аналогично поскольку С'(д) = 2 йрадь ', то 1пеал(С) = ~ (срг = С'(1). (12) И наконец, еще раз применив операцию дифференцирования, получим наг(С) = С" (1) + С'(1) — С'(1)з (13) (см. упр, 2) В формулах (12) и (13) среднее и дисперсия выражены через производящую функцию.
В нашем случае нужно вычислить С'„(1) = А„Из (7) имеем С'.( ) = -С-- ( ) + С'.— ( ) и и С„(1) = -'+ С„,(1). Учитывая начальное условие С((1) = О, находим А„= С'„(1) = ̈́— 1. (14) т Поскольку между целочисленными случайными величинами и производящими функциями существует взаимно однозначное соответствие, ясно, что символы теап(С) и чаг(С) обозначают среднее и дисперсию случайной величины с производящей функцией С вЂ” Прим ред ** (а"! — это коэффициент при ть в разложении функции /(с) в степенной ряд.— Прим, ред.
Это и есть среднее число выполнений шага М4. Для больших п оно приближенно равно !и и (Залсечанищ г-й момент А + 1, т. е. величина 2, ()с + 1)"р„гм есть (сп) (1 — а) ~ ~ с („')(!п1,'с)~"*, что приближенно равно (!пп)" (см Р В. М Вова, САСМ 9 (1966), 342). Распределение вероятностей для величины А впервые было изучено Ф Г. Фостером (Г.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
