Д. Кнут - Искусство программирования том 3 (2-е издание) - 2001 (Часть 1) (1119456), страница 36
Текст из файла (страница 36)
До сих пор никакие методы, которые действительно отличались бы от применявшихся ранее, е)це не использовались, но для анализа ряда Т„потребуется новая идея, основанная на простых принципах теории функций комплексного переменного. Если х — произвольное положительное число, то 1 г)~э+' ' 1 е' * = —, / Г(т)х "4г = — / Г(-+11)х ) у +'))(1. (42) ! /т-и< -СС Для доказательства этого тождества рассмотрим путь интегрирования, показанный на рнс. 20, (а), где й)„Х' и М велики. Значение интеграла вдоль этого контура равно сумме вычетов внутри контура, а именно .-~-) йш(,+й)Г(,)= ~ .'(-',) .
о<ь<м о<ь<м Интеграл по верхнему отрезку контура есть О() )Г(1+(Х)(я ')11), и имеется хорошо известная оценка Г(~ч-и') = О(Ь ~И~~'-'~' -'- "~'),р, Х (Свойства гамма-функций рассматривая)тся, например, в книге ЕгйеЗу1, Ыайппз, ОЬегЬетыпкег апб Тг)сошй ЩЛег Тгапзсепдепгв) Гппсг1опв 1 (Хеи Ъог(с Мага)гНй!, 1953), СЬарсег Ц Поэтому интегралом по верхнему отрезку можно пренебречь: О(е "л~т )' (К~те)» й).
Интеграл по нижнему отрезку ведет себя столь же без- <л з )~з обидно. Для вычисления интеграла по левому отрезку контура воспользуемся тем фактом, что Г(2+И-М) = Г(-+тг)/(-М+ -'+М)... (-1+ 1+г1) = Г(1+ 11) О(1!(М вЂ” Ц(). Следовательно, интеграл по левой стороне есть г о) "-'~'))и-с~)/ г)-~'о/а. Поэтому прн М, д), Х' -~ оо уцелеет лишь интеграл по правой стороне; тем самым доказано тождество (42). В действительности тождество (42) остается в силе и в том случае, если заменить -' лк)бым положительным числом. -- ь1 з т Рис, 20.
Контуры интегрирования лля тождеств с гамма-функциями. (44) 1/(2 ' ' — 1) = -~ '/1~2 — $+0(~). Вычет в точке з = -1 равен коэффициенту при и1 ' в произведении этих трех формул, а именно 1 — (!Пп + у — 1)/)п2. Прибавляя остальные вычеты, получаем формулу Т !Пи+7-1 1 -М --+3(п)+ — +О(п ) (46) и !П2 2 и Рассуждая аналогично, можно вывести и другие полезные соотношения, содер- жа1цие гамма-функции. Величину л ' можно заменить другими функциями от с; можно также заменить другой величиной константу -'. Например, 1 г ~1~+1 — 1(с)х 1Ь вЂ” е — 1+ т, (43) -З)З-1 а это — критическая величина в формуле (41) для Т„; 1 г-зуз+йй Т = ~; —.~ Г( И Ф) ' '1(.
У>1 -З~Э-1 Суммирование можно внести под знак интеграла, так как сходимость здесь доста- точно хорошая. Имеем (пр1)й пй ~~~ '(! 12й)1 пиу(2й 1) если И(н1) > !) 1>1 1>1 поскольку !2 ( = 2и1 ! > 1. Поэтому и г-э/э+йй Г(с) и-1- (45) 2я1 1 и остается оценить последний интеграл, На этот раз интегрирование производится по контору, который больше вытя- нут енраео, как изображено на рис. 20, (Ь).
Интеграл по верхнему отрезку есть 0(п11эс ™~э ) !М+1й1!' Й), если 2не ЭЕ 1, а интеграл по нижнему отрезку также пренебрежимо мал, когда Х и 11". значительно больше, чем М. Интеграл по правому отрезку равен 0(п ' и ) )Г(М + И)) й). Зафиксировав М и устремив Х, 11' -1 оо, можно показать, что -Т„~п есть О(п ' м) плюс сумма вычетов в области -3~2 ( Я(с) с М. Иоэффнцнент Г(э) имеет простью полюсы при с = -1 и э = О, в то время как и ' ' не имеет полюсов, а 1Д2 ' " — 1) имеет простые полюсы при э = -1 + 2л13~1П 2, Наибольшую трудносгь представляет двойной полюс в точке с = -1. если П1 = э + 1 мал6, то можно воспользоваться известным соотношением Г(г+ 1) = ехр(-тз+ ('(2)э'/2 — ~(3)эз/3+ ~(4)л'(4-" ), где Цэ) = 1 '+ 2 '+ 3 '+ = Н~ ), для вывода следующих разложений: Г(э) = Г(н1 + 1) = -е1 ' + ( у — 1) + 0(п1), П1(н1 — 1) и ' ' =1-ш!Пи+О(и1э), для любого большого М, где д(п) — функция довольно необычного вида: д(п) = — ~~> 81(Г( — 1 — 2к1?с/!г>2) ехр(2хг?г18п)).
2 !П2 „м (47) Заметим, что Ю(п) = 5(2п). Среднее значение д(п) равно О, так как среднее значение каждого слагаемого равно О. (Можно считать, что величина ()8п) шоб 1 имеет равномерное распределение, принимая во внимание результаты, которые илгек>т отношение к числам с г>лавагг>щей точкой, полученные в разделе 4.2.4.) Кроме того, поскольку !Г(-1+ И)! = !х/(1(1+ гз) ашЬ х?)~>?з, нетрудно показать, что !б(п) ! < 0.000000173. (8) Таким образом, в практических приложениях Б(п) можно спокойно отбросить.
Что касается теории, то без б(п) получить асимптотический ряд для (?„невозможно; именно поэтому анализ величины (?„довольно затруднителен. Из определения Та в (41) немедленно следует, что Тзо То 1 — = — + 1 — — + —. 2п и и и (49) Таким образом, слагаемым 0(п м)> представляющим ошибку, в выражении (46) нельзя пренебречь и заменить его нулем. Однако в упр.
54 предлагается другой подход к анализу, при котором удается избежать появления такого слагаемого, сформировав довольно необычный сходящийся ряд. Итак, сумма (38) сведена к слсдующелгу выражению: / у — 1 1 с?о =и!8п+и ~ — — +Б(п) +0(1). !п2 2 (50) Метод гамма-функций, который использовался для получения этого результата, представляет собой частный случай более общего метода преобразования Молли>га, которое исключительно полезно для анализа рекуррентных методов, связанных с поразрядным представлением. Другие примеры применения этого метода гамма- функций можно найти в упр, 51-53 и в разделе 6.3. Прекрасным введением в преобразования Меллима и его приложения для анализа алгоритмов является работа Р.
Р!а)о!ес, Х. Соцгдоп апд Р. П>нпав, ТЛеогеИса! Со>присос Вс!енсе 144 (1995), 3-58. УПРАЖНЕНИЯ 1. (ММГ>) Пусть а>... а„— перестановка множества (1,..., п) и пусты и у таковы, что г < у и а, > а>, Пусть а>... а'„— перестановка, которая получается из а>...
а„, если поменять местами а; и а>. Может ли в а>>... а'„быть больше инверсий, чем в а>... а„? ° 2. [Мйо] (а) Каково минимальное число обменов, необходимых для того, чтобы рассортировать перестановку 376981452? (Ь) В общем случае пусть дана перестановка х = а>... а„множества (1,..., и) н пусть хсЬ(х) — минимальное число обменов записей, в результате которых пере стагювка х будет рассортирована в порядке возрастания. Выразите хсЬ(;г) через "более простые" характеристики перестановки гг (см. упр. 5.1А-41), 8. (10) Является ли >стойчивой сортировка методом пузырька (а>чгорнтм В)? 4. [МЯУ] Если на шаге В4 получится г = 1, то н» самом деле работу алгоритма В можно сразу же заканчивать, потому по на следующем шаге В2 не вьшолнится никаких полезных действий.
Какова вероятность того, что при сортировке случайной перестановки иа шахе В4 окажется $ = 12 б, [МИЬ] Пусть 6| 6« 6~ — таблица инверсий перестановки а~ аю .. а . Покажите, что после г проходов сортировки методом пузырька значение переменной ВООИО будет равно шах (Ь; +1 ] Ь; > г) — г при О < г < шах (Ьм..., 6„). б.
[М88] Пусть ам .. а — перестановка множества (1,..., и) и пусть а',... а'„— обратная к ней перестановка. Покажите, что чисэо проходов, необходимых для того, чтобы рассортировать а~... а„методом пузырька, равно 1+ шах(а[ — 1, оэ — 2,..., а'„— и). 7. [М88] Вычислите стандартное отклонение числа проходов при сортировке методом пузырька и выразите его через и и функцию Р(п). [Ср, с формулами (б) и (7).] 8. [МЯ4] Выведите формулу (8). 9.
[М48] Проанализируйте число проходов и число сравнений в алгоритме шейкер-сор- тировки. (Замечание. Полезная информация содержится в упр. 5.4.8-9.) 10. [Мйб] Пусть а~ аг...а„— 2-упорядоченная перестановка множества (1,2,..., и). а) Каковы координаты конечных точек а;-го шага соответствующего пути на решетке (см. рис. 11 на с. 10б)2 Ь) Докажите, что сравнение и/илн обмен элементов а~.ап аэ;аз,, соответствует перегибанию пути относительно диагонали, как на рис. 18, (Ь), с) Докажите, что сравнение и/кяи обмен элементов а«:аггю аэ:а«+ю ... соответствует перегибанию пути относительно линии, расположенной на н«единиц ниже диагонали, как на рис.
18, (с), (д) и (е), если 8 = 2т — 1. ° 12, [МЯЬ] На какой перестановке множества (1,2,...,18) достигается максимум числа обменов записей в алгоритме Бэтчерау 12. [84] Напнпппе 812-программу для шпоритма М, предполагая, что 812 — компьютер, в системе команд которого имеются команды АИО н 888, Сколько времени потребуется такой программе, чтобы рассортировать шестнадцать записей из табл. 12 13. [10] Устойчива ли сортировка Бэтчерау 14.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
