до тех пор, пока средняя часть не станет пустой. Затем нужно перебросить две крайние части в середину.

D1. [Начальная установка.] Установить а <г- b <г- I, d г.

D2. [Увеличивать b до тех пор, пока не станет Кь > К.] Если b < с и Кь < К,

увеличить 6 на 1 и повторить этот шаг. Если b < с и Кь = К, выполнить обмен

До <+ Яь, увеличить а и 6 на 1 и повторить этот шаг. D3. [Уменьшать с до тех пор, пока не станет Кс < К.] Если b < си Кс > К, уменьшить

с на 1 и повторить этот шаг. Если b < с и Кс = К, выполнить обмен Rc Rd,

уменьшить с и d на 1 и повторить этот шаг.

D4. [Замена.] Если b < с, выполнить обмен Яь f+ Дс, увеличить 6 на 1, уменьшить с на 1 и вернуться к шагу D2.

D5. [Очистка.] Выполнить обмен Ri+k f+ Rc-k при О < к < min(a - l,b - а); также выполнить обмен Rb+k <+ Rr-k при О < к < min(d - с, г - d). Окончательно установить ii-1 + Ь - а, jr - d + c.

Совершенно очевидная модификация на шаге D1 должна обеспечить эффективную обработку вырожденных случаев и обеспечить a<b-ac<d до перехода к D2. Тогда исчезнет необходимость в проверках "6 < с" на шагах D2 и D3 (см. упр. 24). Более того, подобная замена позволит избежать обмена записи с самой собой.

Одно из приложений сортировки - сбор записей с равными ключами вместе. Таким образом, разделение на три части зачастую более предпочтительно, чем разделение на две части, предусматриваемое алгоритмом Q. Операции обмена на шаге D5 выполняются эффективно, поскольку все записи с ключами, равными К, к этому времени уже заняли свои окончательные позиции.

Это упражнение придумано В. Г. И. Фейеном (W. Н. J. Feijen), который назвал его "проблемой голландского флага": "Задано множество объектов красного, белого и синего цветов, случайным образом разбросанных между тремя колонками. Нужно придумать способ взаимного обмена пар объектов таким образом, чтобы красные собрались в верхней части колонки, а синие - внизу, причем каждый объект должен просматриваться только один раз и разрешается использовать минимальное число дополнительных переменных для управления процессом" [См. Е. W. Dijkstra, А Discipiine of Programming (Prentice-Hall, 1976), Chapter 11*.]

42. Это особый случай теоремы Карпа (см. R. М. Кагр, JACM 41 (1994), 1136-1150, §2.8). Существенно более строгая асимптотическая граница для хвоста распределения при быстрой сортировке была получена в работе С. J. Н. McDiarmid, R. В. Hayward, J. Algorittims 21 (1996), 476-507.

43. При а Он-, как следует из упр. 1.2.7-24, имеем

«-(6- -l)dy + у-е- dy = Г(а) - 1/а = (Г(а + 1) - Г(1))/а Г(1) = -7-

44. При А; > О имеем rfc(m) ~\{2mf+V{{k + \)l2)-6ko-Y.i>o{-iy Bk+2i+il {{k+2j + {2тУ). При А; = -1 вклады от Sk~\m) в (36) взаимно уничтожаются с подобными

членами в разложении Ят-i, и имеем r i(m) = Ят-i -l-(l/\/2m) Ef>o ~ (ln(2m)--

7) - Ej>i(-l)-S2j/(2j)j! (2m)-. Поэтому вклад в W-i члена N/t (33) получается из суммьГтХ;г>1 ехр(-«72т)(1 - t/Zm + t7l8m*)(l - «74т*)(1 - t/2m - t/Sm) + 0(m-V2) imlnm-h (ln2--7)m - %/27rm-- + 0(m-i/2). Член -\N- дает вклад

* Имеется русский перевод: Дейкстра э. В. Дисциплина программирования. - М.: Мир, 1978. - Прим. перев.

-Ef>iexp(-<V2m)(l - <V3m)(l - </2m)(l + </m) + 0(m-V2) = iy2¥+ . Член <5(1 дает вклад i. И наконец, член - l)B2iV~ дает вклад т~ Jj texp(-«Зт) + 0(m-i/2)= i + 0(m-i/2).

45. Рассуждение, использованное при выводе тождества (42), справедливо и для тождества (43), нужно только отбросить вычеты в точках г = -1иг=0.

46. Действуя так же, как при вычислении интеграла (45), получаем {s - 1)!/1п 2 + 6,{п), где

Ss{n) = 53«(r(s - 27ггА;/1п2) exp(27riA;lgn)).

*>1

[Обратите внимание на то, что Г(в + it)f = (По<*<«( + t))ir/{tsmbirt), где я > О - целое, так что можно найти верхнюю границу для функции Ss{n).]

47. Сумма Ej>i е""" {п/2-У на самом деле равна интегралу из упр. 46 при всех s > 0.

48. Воспользовавшись промежуточным тождеством

1-е- = -/ nz)x-dz,

тг У-1/2-too

действуем так же, как описано в тексте, но теперь \ - выполняет роль - 1 -\- х; F„+,/(n + 1) = (-1/27Г0 T{z)n- dzl{2- - 1) + 0(n-»), a интеграл равен Ign +

7/ln2 - I - <5o(n) в обозначениях упр. 46. (Таким образом, величина An из упр. 38 равна iV(l/ln2 - <!io(iV - 1) - 5-x{N)) + 0(1).)

49. Правую часть равенства (40) можно улучшить, заменив ее на (п/х+ х+хО{п~)). Результат выразится в том, что будет вычтена сумма из упр. 47 с коэффициентом и 0(1) в (47) заменится выражением 2 - l/ln 2 + <5i(n)) + 0{п~). (Двойка появилась из "2/п" в (45).)

50. Umn = пlog„ n-Нп((7- 1)/Inm- 1 -Н<5-1 (п)) -Нm/(m- 1) - 1/(2In m) - <5,(n) + 0{п-), где <5«(п) определяется в упр. 46 но In 2 и Ig заменяются на In m и log„,. [Замечание. При m = 2, 3, 4, 5, 10, 100, 1000 и 10* имеем <5 i(n) < .0000001725, .00041227, .000296, .00085, .00627, .068, .153, .341 соответственно.]

51. Пусть N = 2т. Можно распространить суммирование в (35) на все значения < > 1. Тогда сумма будет равна

1 га+гоо , га+гоа

е i / nXtV-t" dz= T{z)N{2z - к) dz

при условии, что а > {к-\- 1)/2. Итак, необходимо знать свойства дзета-функции. Если Щи)) > -q, то {w) = 0(u;+) при u; -+ оо; следовательно, контур интегрирования можно как угодно далеко смещать влево, если только учесть вычеты. Сомножитель Г(г) имеет полюсы в точках О, -1, -2, ..., а (2г - к) имеет полюс лишь в точке z = {к + 1)/2. Вычет в точке z = -j равен (-1)({-2j - к)/j\, а C(-n) = (-l)"B„+i/(n--1). Вычет в точке г = (Л + 1)/2 равен Г{{к + l)/2)iV*+. Но если к = -1, то в точке z = 0 имеется двойной полюс, а (г) = l/{z - 1) -Н 7 -Н 0(г - 1), так что вычет в О в этом случае равен 7-1- i In iV - 57. Таким образом получаем асимптотический ряд, упомянутый в ответе к упр. 44.

52. Положим, что х = t/n; тогда

inlt) /Сп)= М-2п{х/1. 2 + xV3 • 4 + • • •) + {х/2 + х/4 + .--)

-{1/6п){х -X* + ) + ).

Искомую сумму теперь можно представить в виде ряда Ylt>i td{t)e " при различных к. Поскольку ({гУ - Et>i d{t)t~, то, действуя так же, как и в упр. 51, можно вычислить вычеты функции T{z)n{2z - к при А; > 0. Вычет в точке z = - j равен

n-{-iy{B2i+k+il{2j + k+l)flJ\,

а вычет в точке z = {к + 1)/2 равен п+Т{{к + 1)/2)(7 + Inn + \ф{{к + 1)/2)), где 1/1(2;) = T{z)IT{z) = Hz-i-j. Так, например, если А; = О, то J2t>i e~"d(t) = \у/ттп 1пп + (It ~ 1п2)У7т+ 7 + 0(тг") при любом М. Чтобы получить Sn/{), добавьте к этой величине (1пп + 7 + - 1п2)xA7" + 0(n-). (См. упр. 1.2.7-23 и 1.2.9-19.)

53. Пусть q = 1 - р. Обобщая анализ, выполненный в упр. 36, (с), получим, что если

, V/"\ / * п-к , к п-к-,

Xn=an + 2 ,Jl)iP1 +<1Р )Хп,

z„=a„ + g()(-i)*a,(p* + g*)/(i-P*-g*).

Следовательно, можно, как и прежде, найти величины Bn и Слг. Множитель 1- в Bn нужно заменить на pq. Анализ асимптотического выражения для Un выполняется, по существу, так же, как в тексте, причем

Тп= Y1 ()(e-""-l + npV-)

r>l,s>0

= -i. / r(z)n-(p- +q-)dz/{l-p- -q)

= {n/hp){\nn + 7 - 1 + hy2hp -hp + 5{n)) + 0(1),

где hp = -(plnp + glng), hf"* = p{\npY +q{\nqY, a <5(n) = E r()n~"7p, причем суммирование выполняется по всем комплексным числам гф\, таким, что р" +9" = 1-Это последнее множество точек, по-видимому, трудно исследовать в общем случае, но при р = ф~, q = ф" решением будут точки z = (-1)*"*" + ктгг/Ыф. Главный член (nlnn) ip также можно было бы получить из общей формулы ван Эмдена, приведенной в ответе к упр. 29. При р = ф~ имеем l/hp к. 1.503718, по сравнению с I 11/2 ~ 1.442695.

54. Пусть С - окружность радиуса [М + 1)Ь и интеграл по С стремится к нулю при М -¥ оо. (Асимптотическое выражение для Un можно теперь вывести по-новому, разлагая Г(п -Н 1)/Г(п -Н гЪт). Метод, рассматриваемый в этом упражнении, применим ко всем суммам вида

е () (-1)"-V(fc) = 2 / В(п + 1, -.)/(.) dz,

если функция / выбрана обоснованно!) Последняя формула выведена в работе N. Е. Nor-lund, Voriesungen Uber Differenzenrechnung (Berlin: Springer, 1924), §103.)

55. Замените строки 04-06 в программе Q следующим образом.