(m-ty.im-ty

= W 1--exp

V m

Таким образом, нас интересует асимптотическое выражение для суммы

rfc(m)= Y1 е-/™**, fc>-l. (35)

l<t<m

(Суммирование здесь также можно было бы распространить на весь диапазон 1 < t < оо, не изменив при этом значения асимптотического выражения суммы, поскольку, как указано выше, входящие в сумму значения при t > m/+ пренебрежимо малы.)

Пусть дк{х) = гг*е-" и /fc(rr) = дк{х/у/Ъп). По формуле суммирования Эйлера при fc > О получим

е Mt) = / л() +е f iftm) - fi-\Q)) + R„

0<t<m ° j=l

P- Jo

= (vfc)(ri"">l*)=°<""""-

Следовательно, при помощи, по существу, тех же приемов, которые применялись и раньше, можно получить асимптотический ряд для Гк{т), если только А; > 0. Но при fc = - 1 этот метод не годится, так как значение /-i(0) не определено; нельзя также просто просуммировать от 1 до т, так как остаточные члены не дают убывающих степеней т, если нижний предел равен 1. (Именно в этом состоит суть дела, и, прежде чем двигаться дальше, читатель должен убедиться в том, что он хорошо понял задачу.)

Чтобы разрешить эту дилемму, можно положить по определению g-i{x) = (е~ - 1)/х и / 1 = д-\[х/у/2гп); тогда /-i(0) = О и r i(m) нетрудно получить 5Zo<«m/-i(0- Равенство (36) справедливо теперь и при fc = -1, а оставшийся интеграл нам хорошо знаком (см. упр. 43):

-±=\ U{x)dx2----Ux -Idy

V2m Jo Jo Jo У

e-y-1 f"/ e-« , m

= / -dy+ / -dy-In -

Jo У Ji У 2

= -7-lnm+ln2 + 0(e-"/2).

Теперь у нас достаточно формул и фактов для того, чтобы вывести, наконец, ответ, который, как показано в упр. 44, имеет вид

И„ = mlnm + (7+ln2)m-v2++0(n-i/2), т = п + 1. (37)

Этим завершается анализ метода пузырька.

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

(:)(-!)да

к>2

Определить его оказывается гораздо сложнее, чем решить другие задачи об асимптотическом поведении, с которыми мы сталкивались до сих пор; элементарные методы разложения в степенные ряды, формула суммирования Эйлера и т. п. здесь бессильны. Следующий вывод был предложен Н. Г. де Брейном (N. G. de Bruijn).

Чтобы избавиться в формуле (38) от подавляющего влияния больших множителей ()(-1)*, начнем с того, что перепишем сумму в виде бесконечного ряда:

= e(fc) (-1) е (-ф) = Е (2(1 - 2-Г - 2- + я). (39)

к>2 j>l j>l

Если положить X - то член ряда запишется в виде

2(l-2-T-2+n=((l-)"-l+x).

При X <п имеем

(l-)" = exp(nln(l-)) =ехр{-х + хО{п-)), (40)

а это наводит на мысль о том, что следует аппроксимировать (39) рядом

Г„ = (2е-"/2 - 2 + п). (41)

Чтобы подтвердить правомерность такой аппроксимации, рассмотрим разность f/„ - Г„ = Х„+У„, где

Хп= (2(1-2"-)"-2-е-"/) [члены при X > п]

2<п}-

0{пе-") [поскольку О < 1-2 < е ]

2<п-

0{n\ogne~") [поскольку имеется O(logn) членов]

Г„ = (2-(1 - 2~)" - 2-е-"/) [члены при х < п]

2>n~

(е-"/2 0(1)). [вследствие (40)]

2>n-

Ниже будет показано, что эта последняя сумма есть 0(1); значит, f/„ - Г„ = 0(1) (см. упр. 47).

До сих пор никакие методы, которые действительно отличались бы от применявшихся ранее, еще не использовались, но для анализа ряда Г„ потребуется новая идея, основанная на простых принципах теории функций комплексного переменного. Если X - произвольное положительное число, то

1 /•1/2-)-гоо 1 /-оо

е- = - / Г(г)х-Ыг = - / Щ + it)x-/+*Ut. (42)

27Гг Ji/2-icc 27Г

Для доказательства этого тождества рассмотрим путь интегрирования, показанный на рис. 20, (а), где N, N и М велики. Значение интеграла вдоль этого контура равно сумме вычетов внутри контура, а именно

е х-(-=)Дш(. + А:)Г(г)=

0<к<М 0<к<М

Интеграл по верхнему отрезку контура есть 0{J\T{t + iN)\x~ dt), и имеется хорошо известная оценка

Г(< + iN) = 0{\t + i7V*-/2e-*-/2 при TV оо.

[Свойства гамма-функций рассматриваются, например, в книге Erdelyi, Magnus, Oberhettinger and Tricomi, Higher Transcendental Functions 1 (New York: McGraw-Hill, 1953), Chapter 1.] Поэтому интегралом по верхнему отрезку можно пренебречь: 0(е~- (iV/rre)* Л). Интеграл по нижнему отрезку ведет себя столь же безобидно. Для вычисления интеграла по левому отрезку контура воспользуемся тем фактом, что

r(i + it-M)= Г( + it)/{-M + l+it)...{-l + l + it) = r( + it)0(l/(M-l)!). Следовательно, интеграл по левой стороне есть

о(х-1/7(м-1)!) 1 r{\ + it)

Поэтому при М, 7V, 7V оо уцелеет лишь интеграл по правой стороне; тем самым доказано тождество (42). В действительности тождество (42) остается в силе и в том случае, если заменить любым положительным числом.

-гЛг-м1->-f-li-iiV -f-iJVi-\--iM-iN

M+iN

(a) (b)

Рис. 20. Контуры интегрирования для тождеств с гамма-функциями.