Рассуждая аналогично, можно вывести и другие полезные соотношения, содержащие гамма-функции. Величину х" можно заменить другими функциями от z; можно также заменить другой величиной константу . Например,

1 /--З/г-Ьгоо

- / T{z)x-dz = e---l+x, (43)

а это - критическая величина в формуле (41) для Г„:

1 r-Z/2+icx>

= / T{z){nlV)--dz. (44)

j>l J-3/2-ioo

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

(п/2)" = п" (1/2") = 717(2" - 1), если U(w) > О, поскольку 12"! = г**") > 1. Поэтому

2т y 3/2 i,

-З/2+гоо r(z)n-l-

3/2-ioo 2-1--- 1

dz, (45)

и остается оценить последний интеграл.

На этот раз интегрирование производится по контору, который больше вытянут вправо, как изображено на рис. 20, (Ь). Интеграл по верхнему отрезку есть 0(n/e- 2 1- + *- dt), если 2 ф \, & интеграл по нижнему отрезку также пренебрежимо мал, когда N и N значительно больше, чем М. Интеграл по правому отрезку равен 0{п~~ Г(М + it)\ dt). Зафиксировав М и устремив 7V, 7V оо, можно показать, что -Тп/п есть 0{п~~) плюс сумма вычетов в области -3/2 < Щz) < М. Коэффициент r(z) имеет простые полюсы при z = -1 и Z = О, в то время как п~~ не имеет полюсов, а 1/(2-1- - 1) имеет простые полюсы при Z = -1 -ь 27ггА;/1п2.

Наибольшую трудность представляет двойной полюс в точке z = -1. Если W = Z + 1 мало, то можно воспользоваться известным соотношением

r(z + 1) = exp(-7z + С(2)г72 - С(3)273 + C(4)2V4 -•••)=

где C(s) = 1""* + 2-* + 3~* Н----= для вывода следующих разложений:

п- = l-wlnn + Oiw), 1/(2-1-" - 1) = -и>-1/1п 2 - i + 0{w).

Вычет в точке z = - 1 равен коэффициенту при в произведении этих трех формул, а именно i - (Inn + 7 - 1)/In2. Прибавляя остальные вычеты, получаем формулу

для любого большого М, где 6{п) - функция довольно необычного вида:

S{n) = е - 27rifc/ln2) exp(27rifclgn)). (47)

к>1

Заметим, что S{n) = S{2n). Среднее значение S{n) равно О, так как среднее значение каждого слагаемого равно 0. (Можно считать, что величина (Ig п) mod 1 имеет равномерное распределение, принимая во внимание результаты, которые имеют отношение к числам с плавающей точкой, полученные в разделе 4.2.4.) Кроме того, поскольку Г(-1 + it)\ = \тг/{1{1 + f)sinhnt)\/, нетрудно показать, что

(J(n) < 0.000000173. (48)

Таким образом, в практических приложениях 6(п) можно спокойно отбросить. Что касается теории, то без 6{п) получить асимптотический ряд для f/„ невозможно; именно поэтому анализ величины [/„ довольно затруднителен. Из определения Г„ в (41) немедленно следует, что

2п п п п

Таким образом, слагаемым 0(п~), представляющим ошибку, в выражении (46) нельзя пренебречь и заменить его нулем. Однако в упр. 54 предлагается другой подход к анализу, при котором удается избежать появления такого слагаемого, сформировав довольно необычный сходящийся ряд.

Итак, сумма (38) сведена к следующему выражению:

C/„ = nlgn + n (-i+<J(n))+0(1). (50)

Метод гамма-функций, который использовался для получения этого результата, представляет собой частный случай более общего метода преобразования Меллина, которое исключительно полезно для анализа рекуррентных методов, связанных с поразрядным представлением. Другие примеры применения этого метода гамма-функций можно найти в упр. 51-53 и в разделе 6.3. Прекрасным введением в преобразования Меллина и его приложения для анализа алгоритмов является работа Р. Flajolet, X. Gourdon and P. Dumas, TiieoreticaJ Computer Science 144 (1995), 3-58.

УПРАЖНЕНИЯ

1. [M20] Пусть ai...a„ - перестановка множества {1,..., n} и пусть i и j таковы, что i < j и т > aj. Пусть ai...a„ - перестановка, которая получается из ai...a„, если поменять местами т и aj. Может ли в ai... а„ быть больше инверсий, чем в ai... а„?

► 2. [М25] (а) Каково минимальное число обменов, необходимых для того, чтобы рассортировать перестановку 37698145 2? (Ь) В общем случае пусть дана перестановка тг = ai... а„ множества {1,..., п} и пусть хсЬ(7г) - минимальное число обменов записей, в результате которых перестановка тг будет рассортирована в порядке возрастания. Выразите хсЬ(7г) через "более простые" характеристики перестановки тг (см. упр. 5.1.4-41).

3. [10] Является ли устойчивой сортировка методом пузырька (алгоритм В)?

4. [М23] Если на шаге В4 получится t = 1, то на самом деле работу алгоритма В можно сразу же заканчивать, потому что на следующем шаге В2 не выполнится никаких полезных действий. Какова вероятность того, что при сортировке случайной перестановки на шаге В4 окажется t = 1?

5. [М25] Пусть bi Ьг ... Ьп - таблица инверсий перестановки ai аг ... а„. Покажите, что после г проходов сортировки методом пузырька значение переменной BOUND будет равно max {bi + i\bi >r} - г при О < г < max(bi,. ..,b„).

6. [М22] Пусть ai... а„ - перестановка множества {1,..., п} и пусть al ...а - обратная к ней перестановка. Покажите, что число проходов, необходимых для того, чтобы рассортировать ai... а„ методом пузырька, равно 1 + max(ai - 1, аг - 2,... ,а„ - п).

7. [М28] Вычислите стандартное отклонение числа проходов при сортировке методом пузырька и выразите его через п и функцию Р{п). [Ср. с формулами (6) и (7).]

8. [М24] Выведите формулу (8).

9. [М48] Проанализируйте число проходов и число сравнений в алгоритме шейкер-сор-тировки. (Замечание. Полезная информация содержится в упр. 5.4.8-9.)

10. [М26] Пусть ai аг ... а„ - 2-упорядоченная перестановка множества {1,2,..., п}.

a) Каковы координаты конечных точек а;-го шага соответствующего пути на решетке (см. рис. 11 на с. 106)?

b) Докажите, что сравнение и/или обмен элементов ai :а2, аз :а4, ... соответствует перегибанию пути относительно диагонали, как на рис. 18, (Ь).

c) Докажите, что сравнение и/или обмен элементов a2:a2+d, a4:a4+d, ... соответствует перегибанию пути относительно линии, расположенной на тп единиц ниже диагонали, как на рис. 18, (с), (d) и (е), если d = 2т - 1.

► 11. [М25] На какой перестановке множества {1,2, ...,16} достигается максимум числа обменов записей в алгоритме Бэтчера?

12. [24] Напишите MIX-программу для алгоритма М, предполагая, что MIX - компьютер, в системе команд которого имеются команды AND и SRB. Сколько времени потребуется такой программе, чтобы рассортировать шестнадцать записей из табл. 1?

13. [10] Устойчива ли сортировка Бэтчера?

14. [М21 ] Пусть c(N) - число сравнений ключей при сортировке Л элементов методом Бэтчера; оно равно количеству выполнений шага М4.

a) Покажите, что с(2) = 2с(2-) + (t - 1)2" -Ь 1 при t > 1.

b) Найдите простое выражение для с(2) как функцию от t. Указание. Рассмотрите последовательность xt = с(2)/2.

15. [М38] Назначение этого упражнения - проанализировать функцию c(N) из упр. 14 и вывести формулу для c(N), если N = 2 + 2 -\-----h 2, ei > ег > > вг > 0.

а) Пусть a(N) = c(N + 1) - c(N). Докажите, что а{2п) = а{п) + [Ig (2п)\ и а(2п + 1) = а(п) + 1; отсюда

a(N)

= () -r(ei-l) + (ei+e2 + --+e.).

b) Пусть х(п) = а(п) - a([n/2J), так что а(п) = х(п) + х([п/2\) + х([п/А]) + . Пусть

у(п) = а:(1) + х(2) +----h х(п) и z(2n) = у(2п) - а(п), z(2n +1)= у(2п + 1). Докажите,

что c(N+l) = z(N) + 2z([N/2\) + Az([N/A\) + .

c) Докажите, что y(N) + ([N/2] + l)(ei - 1) - 2 + 2.

d) Теперь соберите все вместе и найдите выражение c(N) через показатели ej при фиксированном значении г.