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